法1:多重背包+交替滚动O(n*v*s[k])  普通做法
代码:
cin>>n>>v;
    for(int i=1;i<=n;i++)cin>>vv[i]>>ww[i]>>s[i];

    int old = 1, now = 0;
    for(int i=1;i<=n;i++)
    {
        swap(old, now);
        for(int j=0;j <= v;j++)
            for(int k=0;k<=s[i] && k * vv[i] <= j;k++)
            {
                f[now][j]=max(f[now][j],f[old][j-k*vv[i]]+ww[i]*k);
            }
            //此处是公式推导的,因此为f[now][j]而非f[old][j],与0/1背包不同
    }
    cout<<f[now][v];

法2:交替滚动 0/1背包拆分 O(v * ∑(i=1~n)s[i]) 与普通做法复杂度相似
但是注意ww和vv数组要往大的开 不然容易下标越界.
代码:
cin>>n>>v;
    for(int i=1;i<=n;i++)
    {
        int a, b, s;
        cin >> a >> b >> s;
        while(s--)
        {
            vv[++t] = a;
            ww[t] = b;
        }
    }

    int old = 1, now = 0;
    for(int i = 1;i <= t;i++)
    {
        swap(old, now);
        for(int j = 0; j <= v;j++)
        {
            if(j >= vv[i])f[now][j] = max(f[old][j], f[old][j - vv[i]] + ww[i]);
            else f[now][j] = f[old][j];
        }
    }
    cout << f[now][v];

法3:自我滚动数组 j要从v从大到小枚举 不然无法体现从old->now的过程

法4:二进制拆分优化(0/1背包形式) + 自我滚动******
复杂度O(v * ∑(i=1~n)logs[i])
基本思想:将每一组s[i]个物品按二进制拆分 例如25 = 1 + 2 + 4 + 8 + 10;
且这五个数能组成[1, 25]内任意一个数 且10 <= 2 ^ 4;

核心:空间换时间
把本来代表 物品种类的n 换成代表 一种物品的二进制拆分形式的new_n 则空间需求变大了
完整代码:
#include<iostream>
using namespace std;
int n,v;
const int N=11000;
int vv[N],ww[N],s[N];
int f[N];

int new_n;
int new_vv[N], new_ww[N], new_s[N];

int main()
{
    cin>>n>>v;
    for(int i=1;i<=n;i++)cin>>vv[i]>>ww[i]>>s[i];

    int new_n = 0;
    for(int i = 1;i <= n;i++)
    {
        for(int j = 1;j <= s[i]; j <<= 1)
        {
            s[i] -= j;
            new_vv[++new_n] = j * vv[i];
            new_ww[new_n] = j * ww[i];
        }

        if(s[i])
        {
            new_vv[++new_n] = s[i] * vv[i];
            new_ww[new_n] = s[i] * ww[i];
        }
    }

    for(int i = 1;i <= new_n;i++)
    {
        for(int j = v;j >= new_vv[i];j--)
        {
            f[j] = max(f[j], f[j - new_vv[i]] + new_ww[i]);
        }
    }


    cout<<f[v];
    return 0;
}