算法1

暴力的分成三类

使用一维dp数组,不开v[]w[]数组

C++ 代码

#include <iostream>
#include <vector>
using namespace std;
const int N = 1010;

int f[N], n, m;

struct WUPIN
{
    int v, w;
};

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

    vector<WUPIN> wp;

    for(int i = 1; i <= n; i ++)
    {
        int v, w, s;
        cin >> v >> w >> s;
        if(s < 0)   //01背包模板
        {
            for(int j = m; j >= v; j --)
                f[j] = max(f[j], f[j - v] + w);
        }
        if(s == 0)  //完全背包模板
        {
            for(int j = v; j <= m; j ++)
                f[j] = max(f[j], f[j - v] + w);
        }
        if(s >= 1)  //多重背包二进制优化模板
        {
            wp.clear(); //!!!记得清空wp!!!
            for(int k = 1; k <= s; s -= k, k *= 2) wp.push_back({k * v, k * w});
            if(s > 0) wp.push_back({s * v, s * w});

            for(auto t : wp)
                for(int j = m; j >= t.v; j --)
                    f[j] = max(f[j], f[j - t.v] + t.w);
        }
    }

    cout << f[m] << '\n';

    return 0;
}

算法2

等价的将 01背包,完全背包 转化为多重背包问题求解

N = 1000 这里多重背包需要二进制优化

C++ 代码

#include <iostream>
#include <vector>
using namespace std;
const int N = 1010;

int f[N], n, m;

struct WUPIN
{
    int v, w;
};

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

    vector<WUPIN> wp;

    for(int i = 1; i <= n; i ++)
    {
        int v, w, s;
        cin >> v >> w >> s;
        if(s < 0) s = 1;        //01背包相当于 s[i] = 1 的多重背包
        if(s == 0) s = m / v;   //完全背包相当于 s[i] = m / v[i] 的多重背包

        for(int k = 1; k <= s; k *= 2)
        {
            s -= k;
            wp.push_back({k * v, k * w});
        }
        if(s > 0) wp.push_back({s * v, s * w});
    }

    for(auto t : wp)
        for(int j = m; j >= t.v; j --)
            f[j] = max(f[j], f[j - t.v] + t.w);

    cout << f[m] << '\n';

    return 0;
}