动态规划（多重背包问题）优化版

77 阅读 0 评论 51 点赞

我是靠谱客的博主彩色悟空，最近开发中收集的这篇文章主要介绍动态规划（多重背包问题）优化版，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

上集回顾：动态规划（多重背包问题）_物联网土猫的博客-CSDN博客

我们发现，这样写的话，虽然很简单易懂，但是我们一算复杂度，比o（n方）还要高！这肯定不行的，这要是数据量给到大一点就过不了，那么我们开始考虑优化；

我们发现，我们的每种物品的个数给到了一个大小，但是这个大小我们不知道，那么我们想一个办法，能不能把这多个物品拆分开？然后他们组合起来还是这一个物品呢？

比如：

1 2 4 8 16

31

这个时候我们发现，其实上述两种写法是完全相同的，因为在01背包问题中，我们只要满足取v[i]的条件的时候，我们就会向下取；而我们这里的循环，其实就是111111...一直往前遍历，实质上是01背包问题的多次重复；

但是这个时候，时间就成了问题，因为我们循环每种物品的s个的时候，只要剩余体积大于我们的i的体积，我们就能尝试一次i，这个时候，可能你多次增加i的数量，最优解没有变化，但是却一直循环，这样会造成我们时间的浪费；

我们想出了一种更好的办法来解决这个问题：二进制拆分法；

对于一个数，我们可以写成2的多个倍数与一个数的加和形式，例如如下形式(假设体积为一)：

1 1 1 1 ...... （200个）

1 2 4 8 16 32 64 73

上述两行在01背包问题的遍历里是等价的，因为01背包的遍历就是只要有空闲的空间，我们就向前取，与当前值作比较，从而得到最优解；

上述两行，第一行使用01的话，会造成大量重复，但是使用第二行的话，我们一定能得到一个排列；无论我们的剩余体积有多少，我们总能找到一个更小的体积去查找以此进行替换；

那么让我们看看转换的这步代码；

int cnt=0;//对应下标当前在何位置
for(int i=1;i<=n;i++)
{
int a,b,c;
cin>>a>>b>>c;//正常输我们的体积，价值，数量
int k=1;//用k来递增，参照快速幂
while(k<=c)
{
cnt++;
v[cnt]=k*a;//每次我们的v[i]，w[i]翻倍即可
w[cnt]=k*b;
c-=k;
k*=2;
}
if(c>0)//最后进行一次特判，保证我们的数据无遗漏
{
cnt++;
v[cnt]=c*a;
w[cnt]=c*b;
}
}

类似快速幂的思想，把数量分解，得到的数存起来，这样的话，原来遍历一遍的高达n的复杂度变为logn，同时加上我们之前对01背包的优化，最终得到了我们的代码：

#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=25010;
int v[N],w[N];
int g[2010];
int main()
{
int n,m;
cin>>n>>m;
int cnt=0;//对应下标当前在何位置
for(int i=1;i<=n;i++)
{
int a,b,c;
cin>>a>>b>>c;//正常输我们的体积，价值，数量
int k=1;//用k来递增，参照快速幂
while(k<=c)
{
cnt++;
v[cnt]=k*a;//每次我们的v[i]，w[i]翻倍即可
w[cnt]=k*b;
c-=k;
k*=2;
}
if(c>0)//最后进行一次特判，保证我们的数据无遗漏
{
cnt++;
v[cnt]=c*a;
w[cnt]=c*b;
}
}
n=cnt;//注意，我们的数据进行了扩增，所以n也要变成长度改变后的值
for(int i=1;i<=n;i++)
for(int j=m;j>=v[i];j--)
if(j>=v[i])
g[j]=max(g[j],g[j-v[i]]+w[i]);
cout<<g[m];
}

在这里，我们的N开到25000以上的·原因是：数据中v和w达到2000，log2000大概为12，乘积为24000，开到25000即可；

至此，完结撒花；