当前位置:首页 >> 学科竞赛 >>

名校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] 算法设计如下:

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]} (求最大值)

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;

用这两种算法的前提是我们必须存住 f[i,j] 这一整个二维数组, 但是如果用循环数组的 话怎样输出解呢? 显然, 我们只需要存住一个布尔型的二维数组, 记录每件物品在不同的状态下放或者不 放就可以了。这样一来数组所占的空间就会大大降低。 [解题收获]: 1)在动态程序设计中,状态的表示是相当重要的,选择正确的状态表示方法会直接影 响程序的效率。 2)针对题目的不同特点应该选择不同的解题策略,往往能够达到事半功倍的效果。像 本题就应该把握住"所有的重量值均为整数"这个特点。


相关文章:
名校noip讲义-背包问题思路
名校noip讲义-背包问题思路_学科竞赛_高中教育_教育专区。名校noip讲义-背包问题思路背包问题思路 [问题描述] 在 M 件物品取出若干件放在空间为 W 的背包里,每件...
NOIP名校讲义
NOIP名校讲义_学科竞赛_高中教育_教育专区。NOIP学习...分析:在解决这个问题时,虽然可以通过读入一个数就...(另外一种方法, for i:=1 to n div 2 do ...
背包问题九讲
背包问题九讲背包问题九讲隐藏>> NOIp 讲义 背包问题九讲 multiple1902 背包问题...基本思路这是最基础的背包问题,特点是:每种物品仅有一件,可以选择放或不放。...
动态规划经典案例详解(背包问题)
本文主要从动态规划经典案例——背包问题的动态规划设计思路出发, 结合具体实 例...【实例 2:金明的预算方案(NOIP2006 提高组真题) 】 【题目描述】 金明今天...
多重背包问题
多重背包问题_电脑基础知识_IT/计算机_专业资料。NOIP 信息学 转自:背包问题九...方法是:将第 i 种物品分成若干件物品,其中每件物品有一个系数,这件物品的...
简单背包问题专题
专门针对noip竞赛初学者设计的简单背包问题专题,包括...可以在课堂上作为动态规划思想启蒙的讲义。...优化空间复杂度 以上方法的时间和空间复杂度均为 O...
背包问题题目及含义
基本思路 这是最基础的背包问题,特点是:每种物品仅有一件,可以选择放或不放...由于用单调队列优化的 DP 已超出了 NOIP 的范围,故本文不再展开讲解。我最初...
背包问题 usaco
NOIP复赛冲刺资料集锦10 45页 免费 贪心算法 37页 免费 USACO讲义合集 54页 2...解题想法 视其为背包问题的一般方法是一个容量受限的背包使得放入其中的物品的值...
01背包问题
如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 01背包问题 NOIP基础。背包问题NOIP基础。背包问题隐藏>> 背包问题 背包...
背包问题
基本思路这是最基础的背包问题,特点是:每种物品仅有一件,可以选择放或不放。...由于用单调 队列优化的 DP 已超出了 NOIP 的范围,故本文不再展开讲解。我最...
更多相关标签:
noip2016 | noip2016提高组复赛 | noip2016普及组复赛 | noip2015提高组复赛 | noip吧 | noip2016复赛成绩 | noip2016复赛 | 2016noip复赛成绩查询 |