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

1、背包问题思路 问题描述在M件物品取出若干件放在空间为W的背包里，每件物品的重量为W1，W2Wn，与之相对应的价值为P1,P2Pn。求出获得最大价值的方案。注意：在本题中，所有的重量值均为整数。算法分析：对于背包问题，通常的处理方法是搜索。用递归来完成搜索，算法设计如下：function Make( i 处理到第i件物品 , j剩余的空间为j:integer) :integer; 初始时i=m , j=背包总容量beginif i:=0 then Make:=0;if j=wi then (背包剩余空间可以放下物品 i )r1:=Make(i-1,j-wi)+vi; (第i件物品放入所能得到的价

2、值 )r2:=Make(i-1,j) (第i件物品不放所能得到的价值 )Make:=maxr1,r2end;这个算法的时间复杂度是O(2n)，我们可以做一些简单的优化。由于本题中的所有物品的重量均为整数，经过几次的选择后背包的剩余空间可能会相等，在搜索中会重复计算这些结点，所以，如果我们把搜索过程中计算过的结点的值记录下来，以保证不重复计算的话，速度就会提高很多。这是简单的以空间换时间。 我们发现，由于这些计算过程中会出现重叠的结点，符合动态规划中子问题重叠的性质。同时，可以看出如果通过第N次选择得到的是一个最优解的话，那么第N-1次选择的结果一定也是一个最优解。这符合动态规划中最优子问题的性

3、质。考虑用动态规划的方法来解决，这里的：阶段是：在前N件物品中，选取若干件物品放入背包中；状态是：在前N件物品中，选取若干件物品放入所剩空间为W的背包中的所能获得的最大价值；决策是：第N件物品放或者不放；由此可以写出动态转移方程：我们用fi,j表示在前 i 件物品中选择若干件放在所剩空间为 j 的背包里所能获得的最大价值fi,j=maxfi-1,j-Wi+Pi (j=Wi), fi-1,j这样，我们可以自底向上地得出在前M件物品中取出若干件放进背包能获得的最大价值，也就是fm,w算法设计如下：procedure Make;beginfor i:=0 to w dof0,i:=0;for i:=

4、1 to m dofor j:=0 to w do beginfi,j:=fi-1,j;if (j=wi) and (fi-1,j-wi+vifi,j) thenfi,j:=fi-1,j-wi+vi;end;writeln(fm,wt);end;由于是用了一个二重循环，这个算法的时间复杂度是O（n*w)。而用搜索的时候，当出现最坏的情况，也就是所有的结点都没有重叠，那么它的时间复杂度是O（2n)。看上去前者要快很多。但是，可以发现在搜索中计算过的结点在动态规划中也全都要计算，而且这里算得更多（有一些在最后没有派上用场的结点我们也必须计算），在这一点上好像是矛盾的。事实上，由于我们定下的前提是：

5、所有的结点都没有重叠。也就是说，任意N件物品的重量相加都不能相等，而所有物品的重量又都是整数，那末这个时候W的最小值是：1+2+22+23+2n-1=2n -1 此时n*w2n，动态规划比搜索还要慢|所以，其实背包的总容量W和重叠的结点的个数是有关的。 考虑能不能不计算那些多余的结点那么换一种状态的表示方式：状态是：在前N件物品中，选取若干件物品放入所占空间为W的背包中的所能获得的最大价值；阶段和决策：同上；状态转移方程是：fi,j=maxfi-1,j-Wi+Pi (j+Wi=wi) and (fi,ws=fi-1,ws-wi+vi) then begin输出解；ws:=ws-wi;end;end;writeln;end;用这两种算法的前提是我们必须存住 fi,j 这一整个二维数组，但是如果用循环数组的话怎样输出解呢？显然，我们只需要存住一个布尔型的二维数组，记录每件物品在不同的状态下放或者不放就可以了。这样一来数组所占的空间就会大大降低。解题收获：1）在动态程序设计中，状态的表示是相当重