多重背包就是在完全背包问题上加入个数限制，然而运用的却是01背包和完全背包的思路QAQ

多重背包I-小数据量

问题描述

有 N 种物品和一个容量是 V 的背包。

第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。 输出最大价值。

输入格式 第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。

接下来有 N 行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i 种物品的体积、价值和数量。

输出格式 输出一个整数，表示最大价值。

数据范围 0 < N,V ≤ 100 0 < vi,wi,si ≤ 100

输入样例 4 5 1 2 3 2 4 1 3 4 3 4 5 2 输出样例： 10

思路

小数据量仅仅在完全背包上加个循环，从0-k枚举，时间复杂度相当大

Code

#include <bits/stdc++.h>

using namespace std;

int f[10005];

int main()
{
    int n,m;
    cin>>n>>m;
    int w[10005],v[10005],s[10005];
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i]>>s[i];
    for(int i=0;i<=n;i++)
        for(int j=m;j>=v[i];j--)
            for(int k=0;k<=s[i]&&k*v[i]<=j;k++)
            {
                f[j]=max(f[j],f[j-k*v[i]]+k*w[i]);
            }
    cout<<f[m];
    return 0;
}

多重背包II-大数据

问题描述

与多重背包I没有太大区别，仅仅是数据范围扩大了 0 < N ≤ 1000 0 < V ≤ 2000 0 < vi,wi,si ≤ 2000

题目给出提示：

提示： 本题考查多重背包的二进制优化方法。

思考

我们可以用1和2搭配出0-3之间的任意数， 可以用1，2，4搭配出0-7中的任意数 以此类推，我们可以用1,2,4,8,…,2^n^拼凑出0~2×2^n^-1区间内任意一个数，最后，多重背包就转化成了01背包问题。

举个例子： 我们有100个苹果，选择的方式有101种，但是我们可以把100拆成1，2，4，8，16，32，37，我们可以用这些数字加出0~100范围内的任意一个整数。 可能你会感到疑惑，为什么最后一个数字是37，而不是64。让我们思考一下，假设最后一个数字是64，那我们排列组合之后可以得到127个数字！

把这些苹果的组合看作一个整体，也就是说现在我们有a,b,c,d,e,f,g这七件物品，他们的价值分别是 1，2，4，8，16，32，37，我们可以通过选择要或者不要这七件物品，排列出100只苹果的101种可能。

Code

#include <bits/stdc++.h>

using namespace std;

int f[25000];
int w[25000],v[25000],s[25000];
int main()
{
    int n,m;
    cin>>n>>m;
    int a,b,c;
    int cnt=1;
    for(int i=0;i<n;i++)
    {
        cin>>a>>b>>c;
        int base=1;
        for(;c>=base*2||(c==1&&base==1);base*=2)
        {
            s[cnt]=base;
            w[cnt]=base*b;
            v[cnt]=base*a;
            cnt++;
        }
        if(c>=s[cnt-1]*2)
        {
            s[cnt]=c-s[cnt-1]*2+1;
            w[cnt]=s[cnt]*b;
            v[cnt]=s[cnt]*a;
            cnt++;
        }
    }
    for(int i=0;i<cnt;i++)
    {
        for(int j=m;j>=v[i];j--)
        {
            f[j]=max(f[j],f[j-v[i]]+w[i]);
        }
    }
    cout<<f[m];
    return 0;
}