将多重背包问题通过幂分解转换成0-1背包问题

#include <iostream>
#include <algorithm>

using namespace std;

//一共有1000个物品，每个物品最多拆分成log2000个物品，故N = 1000log2000 = 25000
const int N = 25000;  

int f[N];
int n, m;
int v[N], w[N], s[N];

int main()
{
    cin >> n >> m;

    int cnt = 0;
    for (int i = 1; i <= n; i ++ )
    {
        int a, b, s;
        cin >> a >> b >> s;
        int k = 1;
        while (k <= s)      //幂分解思想，由1,2,4,8,...,512能组成1~1023中所有的数
        {
            cnt ++ ;
            v[cnt] = a * k;
            w[cnt] = b * k;
            s -= k;
            k *= 2;
        }
        if (s > 0)      //扫尾
        {
            cnt ++ ;
            v[cnt] = a * s;
            w[cnt] = b * s;
        }
    }

        n = cnt;    //此处的n即0-1背包中的物品数量，每个物品都不相同

        //接下来就是重复0-1背包的代码
        for (int i = 1; i <= n; i ++ )
            for (int j = m; j >= v[i]; j -- )
                f[j] = max(f[j], f[j - v[i]] + w[i]);

    cout << f[m] << endl;

    return 0;
}