为什么不用二维

因为用二维会受空间限制，😓

const int N = 12010, M = 2010;

N * M * 4 = 96 MB > 64 MB emm，只能用一维来做

朴素一维

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 12010, M = 2010;

int n, m;
int v[N], w[N];
int f[M];
int main()
{
    cin >> n >> m;


    //本质是把多重背包拆成了01背包来处理
    //第i种物品有s个，要枚举s种情况、
    //那我拆成logs个物品来表示这s中情况，对这logs物品01选择
    int cnt = 0;

    for (int i = 0; i < n; i ++ )
    {
        int a, b, s;
        cin >> a >> b >> s;//第一件物品的体积，价值，数量

        int k = 1;//用多个打包物品代替这种物品，初始时，打包物品的数量是1
        while (k <= s)//当打包物品的数目不大于可用总数量时，循环进行
        {
            cnt ++ ;//cnt既表示第cnt个物品，也表示物品的数量
            v[cnt] = a * k;//有k个物品，体积就乘于a(一个物品的体积)。这样就表示一个打包物品的体积
            w[cnt] = b * k;//价值同上
            s -= k;//可用总数减去k
            k *= 2;//打包物品的数目翻倍
        }

        if (s > 0)//还剩s个物品，直接打包成一个
        {
            cnt ++ ;
            v[cnt] = a * s;
            w[cnt] = b * s;
        }
    }

    n = cnt;//最终把cnt赋值给n，让n继续代表的物品数量N * logs


    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;
}

优化输入一维

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 12010, M = 2010;

int n, m;
int v[N], w[N];
int f[M];
int main()
{
    cin >> n >> m;

   for (int i = 1; i <= n; i ++ )
    {
        int v, w, s;

        cin >> v >> w >> s;//第一件物品的体积，价值，数量

        for (int k = 1; k <= s; s -= k, k <<= 1)//用多个打包物品代替这种物品，初始时，打包物品的数量是1
        {
            for (int j = m; j >= k * v; j -- )
                 f[j] = max(f[j], f[j - k * v] + k * w);
        }

        if (s > 0)//还剩s个物品，直接打包成一个
        {
            for (int j = m; j >= s * v; j -- )
                 f[j] = max(f[j], f[j - s * v] + s * w);
        }

    }            
    cout << f[m] << endl;

    return 0;
}