资源背包类型动态规划

《资源背包类型动态规划》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、资源背包类型动态规划资源肯包类型动态规划是动态规划中的经典问题，在近儿年联赛中经常出现，甚至在NOTP2006的铧及组和提高组屮同时出现。因此如何较好地掌握这一问题的解决方法，提升学生的思维能力，成为了一个值得研究的热点问题。本文对资源背包类型问题进行丫系统的分类，对每个子类的背包问题进行丫较深入的算法分析和对比研宄，g在能够深入理解背包问题的内涵、下W主耍讲解三类背包问题，即0-1背包、完全背包、二维背包。一、0-1背包1.经典的背包问题一0-1背包【例题1】0-1背包【问题描述】在0-1背钮问题中，需对容量为C的背钮进行装载。从n个物品中

2、选取装入背包的物品，每件物品i的重量为wi，价位为vi。对于可行的背钮装载，背包中物品的总熏量不能超过背包的容量，最佳装载是指所装入的物品价值鉍高，即vlXxl+v2XX2+."+ViXXi（其1彡i

3、111【样例输出】12【试题特点】每种物品仅有一件，可以选择放或不放，故称作为0-1背包。【思路点拨】第一次看到背包类的问题，容易想到贪心策略，但是贪心策略得不到最优解。从物品上进行贪心，不外乎三个方面：重觉、价值和价值/重:S，下面一一分析：贪心1:对输入数据，以物品重量排序，越轻的越靠前。以样例为例，得到如下表所示的排序结果。物品序号重景价值①21⑥31②47③54④65⑤1011以物品重贵排序得到的结果（越轻的越靠前）根据排序结果，在剩不的物品屮每次选择最轻的装入背包。背包的容萤为11，此吋选择物品的编号为①、⑥、②，得到的总价值为9,

4、而输fli样例的最大价值为12,这种选择显然不对。贪心2:对输入的数据，以物品的价値排序，价值越高的越靠前。以输入样例为例，得到如下表所示的排序结果。物品序号熏量价位⑤1011②47④65③54①21⑥31以物品价格排序得到的结果(价格越髙的越靠前)根据排序结果，在剩下的物品中选择价值越髙的装入背包.此吋可以选择的物品为⑤，得到的总价位为11,小于输出样例12。此方案也不对。贪心3:如果输入数据设置为n=3,m=6,物品里呈依次为3,3,4,价值依次为4,4,7,则按照价值/重》排序，得到如下表所示的排序结果。序号重萤价使价值/重景③471.

5、75①341.33②341.33价值/重量排序表根据背包容量，选择的物品为③，得到的总价位为7:而实际上，此输入数据的最大价位应为8,所以此种贪心也存在反例。由上讨知，三种贪心策略都存在反例，得不到最大价值。其实，背包问题中一个物品只冇两种状态，耍么被放入背包中，耍么不放入背包中，川A1，…，An表示n个物品的状态，当Ai放入背包时，置Ai=l,不放入吋，置Ai=O。对于输入的所有物品，以i=l,2,3，...，n给物品标号，下而逐一分析物品的状态及相应的价位。对于第一个物品，如果A1=O,则问题转变为背包容呈仍为m，在2,3，，..，n个物

6、品屮选择：如果Al=l，则问题转变为背包容ft为m-wl,在2，3，.，.，n个物品中选择，此时最大价值为max{f(m),f(m-wl)+vl)，f(m)表示在背包容觉力m时，在剩下的物品中选择物品的最大价値。第一次决策之后，剩下的问题便是考虑在重量为(m，m-wl}两种情况下选择最优方案的问题了。以此类推，直到所有物品都试探过，得出最大价位。这个问题明显其有最优子结构性质和无后效性，可以使用动态规划方法解决。(1)阶段和状态①以在前i件物品屮选择若干件物品为阶段：②在前i件物品巾，选取若干件物品放入所剩空间力j的背包中所能获得的最人价值力

7、状态：③以放第i件物品或不放第i件物品为决策。设f农示选择前i个物品，背包容量为j吋所获得的最大价值。(2)状态转移方程f[i][j]=max{f[i-l][j],f[i-l][j-w[i]]+v[i](j>=w[i])}初始条件:f[i][O]=f[O][i]=Oanswer=f[n][m](3)核心子程序for(i=l;i〈=n;i++)f[0][i]=0;//初始化for(i=l;i〈二m;i++)f[i][0]=0;//初始化for(i=l;i〈=n;i++)//阶段，前i个物品for(j=l;j<=m;j++)//状态j的重量{f[

8、i][j]=f[i-l][j];if(j>=w[i]&&f[i][j]〈f[i_l][j-w[i]]+v[i])f[i][j]=f[i-l][ji[i]]+v[i]