多重背包的二进制优化
今天在写到多重背包的题的时候，本来想着按老方法一个个循环添加，没想到这次超时了，就找下了下优化的方法，果然找到了
二进制优化
不得不说是真的牛逼，智商差距啊 智商差距啊！
好了，下面正题
首先，之前的方法是这样的
假如我们 东西的价值是 Val[] 数组，对应数量是 Num[]数组 ，一共有 n件东西
那按照老方法是 把数量大于一件的，全部抽出来添加在 Val[]数组，也就是说我们把这些大于一件的东西，全部当成 新的一件并且价值相同的 东西。代码如下：
#include<iostream> using namespace std; int main() { int n; int wei[100], val[100], num[100];//物品的重量、价值、数量 cin >> n;//读入一共有几种物品 //读入物品的信息 for (int i = 1; i <= n; i++) { cin >> wei[i] >> val[i] >> num[i]; } //下面是核心 int tail = n; //从第一件产品开始枚举 for (int j = 1; j <= n; j++) { while (num[j]!=1)//如果该件产品的数量不是1件的话 { tail++;//尾部加一 //添加在尾部，补充好物品的信息 wei[tail] = wei[j]; val[tail] = val[j]; num[tail] = 1; } } return 0; }
这种方法应该也就我这种脑子想的，其实还有点问题，就是如果物品数是0的话，还得再加一个判断把该物品删除了。
然后就是TLE了，所以下面是优化的方法！
——————————————————分割线——————————————————————————————
二进制优化。
简单来说，就是把一个数字分成 （1 2 4 8.........最大数） 这样下去的类型
为什么呢？ 因为这些数字可以组成（1~最大数）中的任何一个数
这也就意味着，我们可以实现组合
其实思路还是和上面的一样，还是把这些抽出来变成一个新的产品，不过 重量和价值 有所不同。
例如变成：
一件 val[i]*1 wei[i]*1
一件 val[i]*2 wei[i]*2
一件 val[i]*4 wei[i]*4
一件 val[i]*8 wei[i]*8
以此类推，这样比如我们要放 该产品4件 那就可以用我们 之前抽出来的变成的 新产品 代替。
for (int i = 1; i <= spe; i++) { //核心代码 for (int j = 1; num[i] > j; j <<= 1)//注意j用到二进制位移 { sale[++count] = sale[i] * j; wei[count] = wei[i] * j; num[i] -= j; } wei[i] = wei[i] * num[i]; sale[i] = sale[i] * num[i]; }
查看5道真题和解析