题目描述

有 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

算法1

(暴力) $O(n^3)$

会超时
直接用完全背包板子

C++ 代码

#include <iostream>

using namespace std;

const int N=1010,M=2010;

int f[N][M];
int v[N],w[N],s[N];
int n,m;

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i]>>s[i];

    for(int i=1;i<=n;i++)
      for(int j=0;j<=m;j++)
        for(int k=0;k<=s[i]&&j>=k*v[i];k++) 
          f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]); 

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

    return 0;
}

算法2

(二进制优化) $O(N*m)=O(1e7)$

所谓二进制优化就是：把每一堆划分为若干小堆，且这若干小堆的的件数均为2的幂次方（最后一堆可能是，也可能不是）
我举个例子 比如 5，它现在就1堆且这一堆里有5件东西，那么我可以从该堆里面取的件数为0、1、2、3、4、5.
如果是二进制划分转换为01背包的话：二进制划分将这一堆分为三堆：1 2 2
从这三堆里面按01背包取东西，可取的件数还是: 0、1、2、3、4、5。
所以我们可以通过二进制优化将该题转为01背包去求解

C++ 代码

#include <iostream>

using namespace std;

const int N=11000,M=2100;

int f[M];
int v[N],w[N];
int n,m;

int main(){
    cin>>n>>m;
    int t=1;
    while(n--){
       int vi,wi,si; 
       cin>>vi>>wi>>si;
       int k=1;
       while(si>=k) { // 当剩余的 大于等于 要拿的 
           v[t]=vi*k;
           w[t]=wi*k;
           si-=k;
           k*=2;
           t++;
       }
       if(si!=0){
           v[t]=vi*si;
           w[t]=wi*si;
           t++;
       }
    }

    n=t-1;
    // 已经转化为 01背包。n堆物品 对于其中某一堆:要吗拿且全拿，要吗不拿

    for(int i=1;i<=n;i++)
      for(int j=m;j>=v[i];j--)
        f[j]=max(f[j],f[j-v[i]]+w[i]);

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