我们都知道多重背包可以转化为01背包来做,最朴素的就是直接通过枚举个数来判断。
不过通过二进制优化,可以节省一些时间。
二进制是一个神奇的东西,应用到计算机里面有很多的妙用。
二进制优化的原理如下:
1、2、4可以组合出所有小于8的数;
1、2、4、8可以组合出所有小于16的数。
……
例如,一个数10,我可以分成1、2、4、3。这样就将原本的10个价值相同的物品转化为价值不同的4个物品了。
不过通过二进制优化,可以节省一些时间。
二进制是一个神奇的东西,应用到计算机里面有很多的妙用。
二进制优化的原理如下:
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; }