题目描述

二进制优化多重背包问题，因为数据量大，普通的多重背包已经无法求解。使用二进制优化。

比如一个物品有9件，体积为V， 价值为W，那么可以把它重新划分成四部分1 2 4 2， 加起来等于9，就是7 + 2 = 0111 + 2， 每部分的体积价值相应地乘以V，W，不是当成一个物品有9件，而是有四个不同的物品，每个只有一件。通过这样子把件数给“抹去”，化为01背包问题减少计算量，01背包的时候可以凑成用1,2,3…9件。

如果按照算法1所示的代码，9是1001，那么会划分为1件、8件，后面再01背包的话，只能选择取1件、或者8件、或者1+8=9件。所以这样子虽然可以压缩状态，但是不能表示出所有的状态，所以会WA。

所以要把N件数表示成 0111…1 + X的形式，01背包的时候可以凑成用1,2,3…N件。如 9 = 7+2 = 0111 + 2。

代码1 这样子不行

//这样子不行
for (int i = 1, v, w, s; i <= N; i++) {
        cin >> v >> w >> s;
        int base = 1;
        while (s) {
            if (s & 1)
                vw[cnt][0] = base*v, vw[cnt][1] = base*w;
            s >>= 1;
            base <<= 1;
            cnt++;
        }
    }

AC代码

#include <cstdio>
#include <iostream>
using namespace std;
int main(){
    int N, V, cnt = 1;//v是体积 W是价值
    int vw[12000][2] = {{0}};
    //一共N个物品，每个物品log s种状态，而s<2000<2^12; 所以共N*logs< 1000*12 = 12000
    int dp[2002] = {0};
    cin >> N >> V;
    for (int i = 1, v, w, s; i <= N; i++) {
        cin >> v >> w >> s;
        int base = 1;
        while (s >= base) {
            vw[cnt][0] = base*v, vw[cnt++][1] = base*w;
            s -= base;
            base <<= 1;
        }
        if (s) {
            vw[cnt][0] = s*v, vw[cnt++][1] = s*w;
        }
    }
    //01背包
    for (int i = 1; i <= cnt; i++) {
        for (int j = V; j >= 1; j--) {
            if (j >= vw[i][0])
                dp[j] = max(dp[j], dp[j-vw[i][0]] + vw[i][1]);
        }
    }
    printf("%d\n", dp[V]);
}