多重背包问题

多重背包问题

暴力拆解。（不推荐

多重背包可以看作0 1 背包，将多重背包拆开存放。

#include
using namespace std;
int a[10005], b[10005];

int main()
{
    int t = 0, n, m, dp[10005] = { }, w, v, s;
    cin >> n >> m;
    while(n -- )
    {
        cin >> v >> w >> s;
        while(s -- ) 将多重背包拆开存放。
        {
            a[++t] = v;
            b[t]  = w;
        }
    }
    for(int i = 1; i <= t; i ++)  0 1 背包模板
    for(int j = m; j >= a[i]; j --)
    dp[j] = max(dp[j - a[i]] + w[i], dp[j]);
    cout << dp[m] << endl;
}

精巧拆解 ：

可知， 任何一个数都可以化成 ： 几个二进制数 + 减去二进制后余下的数。

则 ，我们将每一个物品的数量都拆解成以上格式。

就又变成了 0  1 背包问题。

#include
#include
#include
using namespace std;

const int N = 2010;

int f[N], n, m;

struct good 
{
    int w, v;
};

int main()
{
    cin >> n >> m;
    vector Good;
    for(int i = 1; i <= n; i ++ )  拆分操作。
    {
        int v, w, s;
        cin >> v >> w >> s;
        for(int k = 1; k <= s; k*=2 )  化为多个二进制数和一个余数。
        {
            s -= k;
            Good.push_back({k * w, k * v});
        }
        if( s > 0) Good.push_back({s * w, s * v});
    }
    for(auto t : Good)
    for(int j = m; j >= t.v; j -- )
    f[j] = max(f[j], f[j - t.v] + t.w);

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