本文共 1854 字，大约阅读时间需要 6 分钟。

一.题目链接：

二.题目大意：

多重背包

三.分析：

做个笔记，偷笑.

立下 flag：这次我要学好 DP！！！

四.代码实现：

二进制优化

#include 
   
    using namespace std;const int M = (int)2e3;int dp[M + 5];struct node{    int v, w;};vector 
    
      vec;int main(){    int n, m;    cin >> n >> m;    for(int i = 1, v, w, s; i <= n; ++i)    {        cin >> v >> w >> s;        for(int j = 1; s >= j; j<<= 1)        {            s -= j;            vec.push_back({v * j, w * j});        }        if(s)   vec.push_back({v * s, w * s});    }        for(auto i: vec)    {        for(int j = m; j >= i.v; --j)        {            dp[j] = max(dp[j], dp[j - i.v] + i.w);        }    }    cout << dp[m] << "\n";        return 0;}
    
   

单调队列优化

#include 
   
    using namespace std;const int M = (int)2e4;const int inf = 0x3f3f3f3f;int q[M + 5];int dp[M + 5];int cal(int u, int k, int v, int w){    return dp[u + k * v] - k * w;}int main(){    int n, m;    scanf("%d %d", &n, &m);    memset(dp, -inf, sizeof(dp));    dp[0] = 0;    for(int i = 1, v, w, c; i <= n; ++i)    {        scanf("%d %d %d", &v, &w, &c);        for(int u = 0; u < v; ++u)        {            int l = 1, r = 0;            int mx = (m - u) / v;            for(int k = mx - 1; k >= max(mx - c, 0); --k)            {                while(l <= r && cal(u, k, v, w) >= cal(u, q[r], v, w))   --r;                q[++r] = k;            }            for(int p = mx; p >= 0; --p)            {                while(l <= r && q[l] > p - 1)   ++l;                if(l <= r)  dp[u + p * v] = max(dp[u + p * v], p * w + cal(u, q[l], v, w));                if(p - 1 - c >= 0)                {                    while(l <= r && cal(u, p - 1 - c, v, w) >= cal(u, q[r], v, w))  --r;                    q[++r] = p - 1 - c;                }            }        }    }    int ans = 0;    for(int i = 1; i <= m; ++i) ans = max(ans, dp[i]);    printf("%d\n", ans);    return 0;}