教育资源为主的文档平台

当前位置: 查字典文档网> 所有文档分类> 高中教育> 学科竞赛> 名校noip讲义-背包问题思路

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

上传者:石宇强
|
上传时间:2015-04-15
|
次下载

名校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)针对题目的不同特点应该选择不同的解题策略,往往能够达到事半功倍的效果。像本题就应该把握住"所有的重量值均为整数"这个特点。

版权声明:此文档由查字典文档网用户提供,如用于商业用途请与作者联系,查字典文档网保持最终解释权!

下载文档

热门试卷

2016年四川省内江市中考化学试卷
广西钦州市高新区2017届高三11月月考政治试卷
浙江省湖州市2016-2017学年高一上学期期中考试政治试卷
浙江省湖州市2016-2017学年高二上学期期中考试政治试卷
辽宁省铁岭市协作体2017届高三上学期第三次联考政治试卷
广西钦州市钦州港区2016-2017学年高二11月月考政治试卷
广西钦州市钦州港区2017届高三11月月考政治试卷
广西钦州市钦州港区2016-2017学年高一11月月考政治试卷
广西钦州市高新区2016-2017学年高二11月月考政治试卷
广西钦州市高新区2016-2017学年高一11月月考政治试卷
山东省滨州市三校2017届第一学期阶段测试初三英语试题
四川省成都七中2017届高三一诊模拟考试文科综合试卷
2017届普通高等学校招生全国统一考试模拟试题(附答案)
重庆市永川中学高2017级上期12月月考语文试题
江西宜春三中2017届高三第一学期第二次月考文科综合试题
内蒙古赤峰二中2017届高三上学期第三次月考英语试题
2017年六年级(上)数学期末考试卷
2017人教版小学英语三年级上期末笔试题
江苏省常州西藏民族中学2016-2017学年九年级思想品德第一学期第二次阶段测试试卷
重庆市九龙坡区七校2016-2017学年上期八年级素质测查(二)语文学科试题卷
江苏省无锡市钱桥中学2016年12月八年级语文阶段性测试卷
江苏省无锡市钱桥中学2016-2017学年七年级英语12月阶段检测试卷
山东省邹城市第八中学2016-2017学年八年级12月物理第4章试题(无答案)
【人教版】河北省2015-2016学年度九年级上期末语文试题卷(附答案)
四川省简阳市阳安中学2016年12月高二月考英语试卷
四川省成都龙泉中学高三上学期2016年12月月考试题文科综合能力测试
安徽省滁州中学2016—2017学年度第一学期12月月考​高三英语试卷
山东省武城县第二中学2016.12高一年级上学期第二次月考历史试题(必修一第四、五单元)
福建省四地六校联考2016-2017学年上学期第三次月考高三化学试卷
甘肃省武威第二十三中学2016—2017学年度八年级第一学期12月月考生物试卷

网友关注

2014年素质赛评分标准
高中数学竞赛 平面几何问题选讲
高二地理竞赛试题
浙江省高中生化学竞赛预赛有机题(附答案)
“青原镇中学第二届冰雪艺术节”开幕式致辞
高中数学竞赛 平面几何的几个重要定理——梅涅劳斯定理
【全国百强校】云南省师范大学附属中学2015届高三高考适应性月考卷(三)理科综合试题(扫描版)
2015年安徽省生物学竞赛预赛试卷(含答案,可编辑版)
2015浙江省数学竞赛参考答案
第一幕
2014年辽宁省中学生生物学竞赛试题及答案
2015年浙江省高中数学竞赛试卷参考答案
2014年全国中学生生物学联赛试题 含答案及解析
2015年浙江省高中数学竞赛试卷及参考答案
2015年安徽省中学生生物学竞赛预赛试卷(word版)
浙江省高中数学辅导课时安排
2015年安徽省中学生生物学竞赛预赛试卷(word版)
南安
高中数学联赛
2015年浙江省数学竞赛试题及答案
学生版版高二竞赛辅导4.12
高中数学竞赛 平面几何的几个重要定理——塞瓦定理
报告改定
我爱奥赛网2006年第二届“我爱奥赛杯”高中化学竞赛试题
高中数学竞赛 平面几何的几个重要定理——托勒密定理
2000年全国中学生生物学联赛理论试卷
NOIP名校讲义
2000年全国中学生生物学联赛理论试卷及参考答案
华山中学艺术展演活动通知
高中数学竞赛 平面几何讲座第5讲 三角形的五心

网友关注视频

【部编】人教版语文七年级下册《老山界》优质课教学视频+PPT课件+教案,安徽省
冀教版小学数学二年级下册第二周第2课时《我们的测量》宝丰街小学庞志荣.mp4
第五单元 民族艺术的瑰宝_15. 多姿多彩的民族服饰_第二课时(市一等奖)(岭南版六年级上册)_T129830
冀教版小学数学二年级下册第二单元《有余数除法的竖式计算》
七年级英语下册 上海牛津版 Unit3
第12章 圆锥曲线_12.7 抛物线的标准方程_第一课时(特等奖)(沪教版高二下册)_T274713
三年级英语单词记忆下册(沪教版)第一二单元复习
【部编】人教版语文七年级下册《逢入京使》优质课教学视频+PPT课件+教案,辽宁省
30.3 由不共线三点的坐标确定二次函数_第一课时(市一等奖)(冀教版九年级下册)_T144342
第19课 我喜欢的鸟_第一课时(二等奖)(人美杨永善版二年级下册)_T644386
【部编】人教版语文七年级下册《过松源晨炊漆公店(其五)》优质课教学视频+PPT课件+教案,江苏省
沪教版八年级下册数学练习册20.4(2)一次函数的应用2P8
沪教版牛津小学英语(深圳用) 五年级下册 Unit 10
沪教版牛津小学英语(深圳用) 四年级下册 Unit 12
外研版英语七年级下册module1unit3名词性物主代词讲解
沪教版牛津小学英语(深圳用) 四年级下册 Unit 8
《空中课堂》二年级下册 数学第一单元第1课时
北师大版数学 四年级下册 第三单元 第二节 小数点搬家
外研版英语三起6年级下册(14版)Module3 Unit2
沪教版八年级下册数学练习册21.3(3)分式方程P17
冀教版小学数学二年级下册1
冀教版小学数学二年级下册第二单元《租船问题》
冀教版英语三年级下册第二课
七年级下册外研版英语M8U2reading
沪教版牛津小学英语(深圳用) 五年级下册 Unit 12
沪教版牛津小学英语(深圳用) 四年级下册 Unit 7
青岛版教材五年级下册第四单元(走进军营——方向与位置)用数对确定位置(一等奖)
飞翔英语—冀教版(三起)英语三年级下册Lesson 2 Cats and Dogs
沪教版八年级下册数学练习册21.3(2)分式方程P15
二年级下册数学第三课 搭一搭⚖⚖