二进制拆分优化多重背包
我们都知道多重背包可以转化为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;
}
投递阿里云等公司10个岗位