多重背包问题 二进制优化 模板

多重背包问题,其实就是多个0-1背包问题.但如果直接使用0-1背包来做的话,时间复杂度会非常高,这时候就需要二进制优化,可以可以将数量为10的物品拆成1 2 4 3.

#include <bits/stdc++.h>
using namespace std;

using PII = pair<int, int>;
const int N = 2005;

int dp[N];

int main() 
{

#ifndef ONLINE_JUDGE
    freopen("D:/VS CODE/C++/in.txt", "r", stdin);
    freopen("D:/VS CODE/C++/out.txt", "w", stdout);
#endif
    int n, v;
    cin >> n >> v;

    vector<PII> goods;

    for (int i = 0; i < n; ++i) {

        int vol, w, s;
        cin >> vol >> w >> s;

        for (int j = 1; j <= s; j *= 2) {

            goods.push_back({
   j * vol, j * w});
            s -= j;
        }
        if (s > 0)
            goods.push_back({
   s * vol, s * w});
    }

    for (auto item : goods) {

        for (int j = v; j >= item.first; --j) {

            dp[j] = max(dp[j], dp[j - item.first] + item.second);
        }
    }

    cout << dp[v];

    fclose(stdin);
    fclose(stdout);
    return 0;
}