题目描述

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

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

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

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

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

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

数据范围
0<N≤1000
0<V≤2000
0<vi,wi,si≤2000
提示：
本题考查多重背包的二进制优化方法。

样例

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

背包

01背包 https://www.acwing.com/activity/content/code/content/252394/

每个背包有多少个可用，拆为一个一个的，就是01背包，但是这里数目比较多，会超时
优化：二进制拆法

首先考虑：例如给数字7，怎样用较少的数字可以表示7以内的所有数
有k个数，每个数取或不取，有2^k种方案，那么log以2为底8，上取整，就是表示7最少需要的数
即1，2，4满足条件
如果数字为10，则需要四个数，但是1，2，4，8可以表示0~15，但是11~15是不需要的，而1，2，4可以表示0~7，那么1，2，4，3可以表示0~10，那么10个物品就可以不用拆成10份，而是拆成4份，就不回超时了。在10-1-2-4，再要-8时，会变成负数，那么这个时候把-4后剩余的数拿过来就可以了。现在就是01背包问题，划分后的每一堆物品选还是不选

C++ 代码

#include<iostream>
#include<vector>
using namespace std;

const int N=2010;

int n,m;
int f[N];

struct Good{
    int v,w;
};

vector<Good>g;//不知道最后会拆成多少份

int main(){
    cin>>n>>m;
    g.push_back({0,0});//使从下标1开始
    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;
            g.push_back({k*v,k*w});
        }
        if(s>0)  g.push_back({s*v,s*w});
    }
    //套01背包模板
    for(int i=1;i<g.size();i++){
        for(int j=m;j>=g[i].v;j--){
            f[j]=max(f[j],f[j-g[i].v]+g[i].w);
        }
    }
    cout<<f[m];
    return 0;
}