Posted by & filed under Uncategorized.

About HuangWencong

Wencong Huang has written 8 post in this blog.

01背包问题。

问题描述:现有背包大小为W,有物品1,2,3.。。。N,大小分别为w1,w2,w3….wN,价值分别为p1,p2,p3….pN,求在背包容量下,能装的最大物品价值。

 

首先我们用最笨的方法,穷举法,N个物品的放入组合一共用2^N种,枚举出每种的价值,取其中大小和小于W的最大值,即为所求,如下:

 

设背包大小W为3,物品1:w1=1,p1=2;物品2:w2=2,p2=3;物品3:w3=3,p3=6;

那么我们的2^3=8种放入的方法分别为:

0

1

2

3

1+2

1+3

2+3

1+2+3

上诉8个组合方法中,1+3,2+3,1+2+3总大小大于背包大小,舍去,于是我们剩余5种方法:

0       权值为:0

1                          2

2                          3

3                          6

1+2                     5

那么我们最后得到的最优方法为只放3号物品,价值为6.

 

上述方法时间复杂度为2^N。

 

下面我们使用动态规划的方法(DP)。

所谓的DP就是记录中间计算结果来简化计算,是一种以空间换时间的方法。

阶段是:在前N件物品中,选取若干件物品放入背包中;

状态是:在前N件物品中,选取若干件物品放入所剩空间为W的背包中的所能获得的最大价值;

决策是:第N件物品放或者不放;

由此可以写出动态转移方程:

我们用f[i,j]表示在前 i 件物品中选择若干件放在所剩空间为 j 的背包里所能获得的最大价值

f[i,j]=max{f[i-1,j-Wi]+Pi (j>=Wi), f[i-1,j]}

 

DP的思想:假设1-N个物品,我们已经求得了1-N-1个物品装入0–W的最优方法,记为f[N-1][0]–f[N-1][W],现在我们老考虑第N个包,我们有两种选择:

  1. 不放入第N个包,那么现在的放入方法不变,即f[N][W]=f[N-1][W].
  2. 放入第N个包,那么我们需要知道W-wN的包大小情况下的最优解,即f[N-1][W-wN],然后放入N,得到f[N][W]=f[N-1][W-wN]+p[N].
  3. 然后我们比较着两种决策的大小,取最大值,即得到上面的公式:

f[i,j]=max{f[i-1,j-Wi]+Pi (j>=Wi), f[i-1,j]}

上面的过程中,我们计算是用到了上一步的一些中间计算结果,避免了重复计算。最后的时间复杂度不难看出,是N*W。

 

我们接着优化其空间复杂度。

上面的算法要用到的空间是数组f[N][W],我们观察到,每次的循环,我们都只用到上一步的结果,那么我们是否可以用一维数组来求解呢?由于每次求解f[i][j],我们都要用到f[i-1][k],其中k<j,那么我们考虑从j到0的循环,只用到一个数组,公式如下:

for i=1..N

for v=V..0

f[v]=max{f[v],f[v-c]+w};

这样我们大大地减少了空间复杂度。具体实现代码如下:

 

接着,我们考虑另一个变种问题,上面并没有要求背包要全部装满,即可以有空余。那么如果我们要求要全部装满又要如何求解?

其实很简单,我们只要把f[0][W]全部设置为负无穷大,那么所有没装满的方法都得不到最大解。

具体代码只需要把

 

我们继续变化问题,上面每种物品只有一个,那么如果每种物品的个数不限又要如何?

其实也不难。如,背包大小为10,物品大小分别为3,4,5,那么物品最多可以放3,2,2个,那么我们的物品序列可以写成3,3,3,4,4,5,5这七个物品,再用上面的方法求解。

Leave a Reply

  • (will not be published)