今天在写到多重背包的题的时候,本来想着按老方法一个个循环添加,没想到这次超时了,就找下了下优化的方法,果然找到了

二进制优化

不得不说是真的牛逼,智商差距啊 智商差距啊!

好了,下面正题

 

首先,之前的方法是这样的

假如我们 东西的价值是  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];
        }