我们都知道多重背包可以转化为01背包来做,最朴素的就是直接通过枚举个数来判断。

不过通过二进制优化,可以节省一些时间。

二进制是一个神奇的东西,应用到计算机里面有很多的妙用。

二进制优化的原理如下:

1、2、4可以组合出所有小于8的数;

1、2、4、8可以组合出所有小于16的数。

……

例如,一个数10,我可以分成1、2、4、3。这样就将原本的10个价值相同的物品转化为价值不同的4个物品了。

伪代码

int n;  //输入有多少种物品
    int c;  //每种物品有多少件
    int v;  //每种物品的价值
    int s;  //每种物品的尺寸
    int count = 0; //分解后可得到多少种物品
    int value[MAX]; //用来保存分解后的物品价值
    int size[MAX];  //用来保存分解后物品体积
    scanf("%d", &n);    //先输入有多少种物品,接下来对每种物品进行分解
    while (n--) {   //接下来输入n中这个物品
        scanf("%d%d%d", &c, &s, &v);  //输入每种物品的数目和价值
        for (int k=1; k<=c; k<<=1) { //<<右移 相当于乘二
            value[count] = k*v;
            size[count++] = k*s;
            c -= k;
        }
        if (c > 0) {
            value[count] = c*v;
            size[count++] = c*s;
        }