多重背包問題 II（二進制優化）

有 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

#include<iostream>
using namespace std;

const int N = 12010, M = 2010;

int n, m;
int v[N], w[N]; //逐一枚舉最大是N*logS
int f[M]; // 體積<M

int main()
{
    cin >> n >> m;
    int cnt = 0; //分組的組别
    for(int i = 1;i <= n;i ++)
    {
        int a,b,s;
        cin >> a >> b >> s;
        int k = 1; // 組别裡面的個數
        while(k<=s)
        {
            cnt ++ ; //組别先增加
            v[cnt] = a * k ; //整體體積
            w[cnt] = b * k; // 整體價值
            s -= k; // s要減小
            k *= 2; // 組别裡的個數增加
        }
        //剩餘的一組
        if(s>0)
        {
            cnt ++ ;
            v[cnt] = a*s;
            w[cnt] = b*s;
        }
    }

    n = cnt ; //枚舉次數正式由個數變成組别數

    //01背包一維優化
    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;
}