名校noip讲义-背包问题思路

名校noip讲义-背包问题思路

背包问题思路

[问题描述]

在M件物品取出若干件放在空间为W的背包里，每件物品的重量为W1，W·2……Wn，与之相对应的价值为P1,P2……Pn。求出获得最大价值的方案。

注意：在本题中，所有的重量值均为整数。

[算法分析]：

对于背包问题，通常的处理方法是搜索。

用递归来完成搜索，算法设计如下：

function Make( i {处理到第i件物品} , j{剩余的空间为j}:integer) :integer;

初始时i=m , j=背包总容量

begin

if i:=0 then

Make:=0;

if j>=wi then (背包剩余空间可以放下物品 i )

r1:=Make(i-1,j-wi)+v[i]; (第i件物品放入所能得到的价值 )

r2:=Make(i-1,j) (第i件物品不放所能得到的价值 ) Make:=max{r1,r2}

end;

这个算法的时间复杂度是O(2^n)，我们可以做一些简单的优化。

由于本题中的所有物品的重量均为整数，经过几次的选择后背包的剩余空间可能会相等，在搜索中会重复计算这些结点，所以，如果我们把搜索过程中计算过的结点的值记录下来，以保证不重复计算的话，速度就会提高很多。这是简单的"以空间换时间"。

我们发现，由于这些计算过程中会出现重叠的结点，符合动态规划中子问题重叠的性质。 同时，可以看出如果通过第N次选择得到的是一个最优解的话，那么第N-1次选择的结果一定也是一个最优解。这符合动态规划中最优子问题的性质。

考虑用动态规划的方法来解决，这里的：

阶段是：在前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]}

这样，我们可以自底向上地得出在前M件物品中取出若干件放进背包能获得的最大价值，也就是f[m,w]

算法设计如下：

名校noip讲义-背包问题思路

procedure Make;

begin

for i:=0 to w do

f[0,i]:=0;

for i:=1 to m do

for j:=0 to w do begin

f[i,j]:=f[i-1,j];

if (j>=w[i]) and (f[i-1,j-w[i]]+v[i]>f[i,j]) then

f[i,j]:=f[i-1,j-w[i]]+v[i];

end;

writeln(f[m,wt]);

end;

由于是用了一个二重循环，这个算法的时间复杂度是O（n*w)。而用搜索的时候，当出现最坏的情况，也就是所有的结点都没有重叠，那么它的时间复杂度是O（2^n)。看上去前者要快很多。但是，可以发现在搜索中计算过的结点在动态规划中也全都要计算，而且这里算得更多（有一些在最后没有派上用场的结点我们也必须计算），在这一点上好像是矛盾的。 事实上，由于我们定下的前提是：所有的结点都没有重叠。也就是说，任意N件物品的重量相加都不能相等，而所有物品的重量又都是整数，那末这个时候W的最小值是：1+2+2^2+2^3+……+2^n-1=2^n -1

此时n*w>2^n，动态规划比搜索还要慢~~|||||||所以，其实背包的总容量W和重叠的结点的个数是有关的。

考虑能不能不计算那些多余的结点……

那么换一种状态的表示方式：

状态是：在前N件物品中，选取若干件物品放入所占空间为W的背包中的所能获得的最大价值；

阶段和决策：同上；

状态转移方程是：

f[i,j]=max{f[i-1,j-Wi]+Pi (j+Wi<=背包总容量), f[i-1,j]}

这样，我们可以得出在前M件物品中取出若干件放进背包在所占空间不同的状态下能获得的最大价值，在其中搜索出最大的一个就是题目要求的解。

算法设计如下：

procedure make;

begin

f[0,wt]:=0;

for i:=1 to n do

for j:=0 to w (背包总容量) do

if f[i-1,j]未被赋过值 then （这些结点与计算无关，忽略）

continue

else

f[i,j]:=max{f[i-1,j+Wi]+Pi , f[i-1,j]};

最大价值：=max{f[n,j]} （求最大值）

名校noip讲义-背包问题思路

j:=1 to w

end;

由于事实上在计算的过程中每一个阶段的状态都只和上一个阶段有关，所以只需要来一个两层的数组循环使用就可以了，这是动态规划中较常使用的降低空间复杂度的方法。

本题能够用动态规划的一个重要条件就是：所有的重量值均为整数 因为

1）这样我们才可以用数组的形式来储存状态；

2）这样出现子问题重叠的概率才比较大。（如果重量是实型的话，几个重量相加起来相等的概率会大大降低）

所以，当重量不是整数的时候本题不适合用动态规划。

[解的输出]：

在计算最大价值的时候我们得到了一张表格（f[i,j]),我们可以利用这张表格输出解。 可以知道，如果f[i-1,j+Wi]+v[i]=f[i,j] (第二个算法)，则选择物品i放入背包。 算法设计1：

进行反复的递归搜索，依次输出物品序号；

procedure Out(i,j:integer);（初始时 i=n, j=获得最大价值的物品所占的空间）

begin

if i=0 then exit;

if f[i,j]=f[i-1,j+w[i]]+v[i] then begin

输出解

Out(i-1,j+w[i]);

end

else

Out(i-1,j);

end;

算法设计2：

同样的思路我们可以用循环来完成；

procedure Out2;

var

i,ws:integer;

begin

ws:=获得最大价值的物品所占的空间;

for i:=n downto 1 do begin

if (ws>=w[i]) and (f[i,ws]=f[i-1,ws-w[i]]+v[i]) then begin

输出解；

ws:=ws-w[i];

end;

end;

writeln;

end;

名校noip讲义-背包问题思路

用这两种算法的前提是我们必须存住 f[i,j] 这一整个二维数组，但是如果用循环数组的话怎样输出解呢？

显然，我们只需要存住一个布尔型的二维数组，记录每件物品在不同的状态下放或者不放就可以了。这样一来数组所占的空间就会大大降低。

[解题收获]：

1）在动态程序设计中，状态的表示是相当重要的，选择正确的状态表示方法会直接影响程序的效率。

2）针对题目的不同特点应该选择不同的解题策略，往往能够达到事半功倍的效果。像本题就应该把握住"所有的重量值均为整数"这个特点。