第4期 王 乐等:基于Matlab的0-1背包问题的动态规划方法求解 89
都把所有子问题的解存于该数组中。对于重复出现的子问题,只有在第一次遇到时才给预求解,并把其答案存放在该数组中保存起来,以便再遇到时可直接引用而不必重新求解,因而可解决所对应的子问题树中的子问题呈现大量重复的问题。
{
for(w=0toW)V[0,w]=0;//将二维数组第一行赋值全零for(i=1ton) for(w=0toW) if(wi!w)
V[i,w]=max(V[i-1,w],vi+(V[i-1,w-wi])//V[i,w]纪录权值至少为w且值最大的子集{1,2, ,n} else
V[i,w]=V[i-1,w];ReturnV[i,W];}
3 解决背包问题的DP算法
3.1 求解过程描述
假定W>0,且两个正整数数组分别为:(v1,v2, ,vn)和(w1,w2, ,wn),期望找到
i=1
#vixi
n
最大且
i=1
#wixi
n
!W的子集为T {1,2, ,n}。采用上述动态
规划思想,解决背包问题的求解过程可描述如下:
步骤一:将问题分解为小的子问题。构造一个二维数组V[0 n,0 W]1!i!n且0!w!W
V[i,w]用来存储权值至少为w且值最大的子集T {1,2, ,n}
即:V[i,w]=max{#vj:T {1,2, ,i},#wj
j T
j T
另外再定义一数组keep[i,K]纪录所选择的物品。当第i个物品选中时,将其赋值为1,否则为0。
K=W
for(i=ndownto1) If(keep[i,K]==1) {
outputi; K=K-w[i] }
!w}
计算出所有满足条件的此二维数组的值,则V[n,W]就包含解决问题的解决方案。
步骤二:根据子问题的解递归定义最优解的值。
设置初始状态集合:
V[0,w]=0当0!w!W,没有任何项目时V[i,w]=- 当w<0, 非法
递归步:
V[i,w]=max(V[i-1,w],vi+(V[i-1,w-wi]),其中1!i!n,0!w!W[3]。
式中:V[i-1,w]为上一轮中重量为w时所求得的价值最大值;vi+(V[i-1,w-wi]表示:选取wi时的价值为vi,此时允许的最大的重量为w,w-wi是还剩下的可承重量。
V[i,w]的取值为V[i-1,w]和vi+(V[i-1,w-wi]中的较大值。如果有i种物品可以选择,而此时所能承受的最大重量为w时,只有两种选择:
%不选新加入的第i种物品。此时只有i-1种物品,最大承受重量为w的最大价值为V[i-1,w]。
&选择新加入的第i种物品。第i种物品的重量为wi的价值为vi,现所能承受的最大重量为w-wi;而i-1种物品还可以选择,此时的最大价值为V[i-1,w-wi];因此价值最大值为(vi+V[i-1,w-wi])。
步骤三:自底向上进行计算V[i,w]。底:V[0,w]=0 当0!w!W;
自底向上计算:使用公式V[i,w]=max(V[i-1,w],vi+(V[i-1,w-wi])。3.2 实现算法
输出i的值即为所选择物品对应的编号。3.3 测试结果
在Matlab6.5[4]环境下对该算法进行测试的过程和结果如下:
>>v=[10403050];w=[5463];n=4;W=10;>>[V,out]=KnapSack(v,w,n,W)V=
0000101010101010 00040404040405050 000004040405070 005050505050509090
out=0204
数组out输出的i值表示物品的编号。结果表明选择第二和第四种物品,所得到的最大价值为90。此算法的时间复杂度为O(nW)[5]。
4 与其他方法的比较与分析
一般来说,用来解决背包问题的方法主要有递归法和贪心法等,但用这两种方法来解决背包问题都有其不可避免的缺点。递归法虽能遍历搜索空间,找到最优解,但由于此问题的解的空间是以级增长的,所以它只适用于解决小规模的背包问题;而贪心法又很难真正找到最优解,即使能找出较优的解也往往与真正的最优解相差很远。如果采用自顶向下的分治法解决此问题,将会随着物品的增多以级规模指数递增,因为分治法要重复计算相同的值。但采用动态规划算法,则可解决重复计算相同内容的问题,以达到减少冗余的根本目的。由于采用的动态规划实质上是一种以空间换时间的技术方法,因此在实现过程
下转第页)
2006 COMPU TER TECHNOLO GY AND DEV ELOPM EN T 基于 Matlab 的 0 - 1 背包问题的动态规划方法求解王 ,王世卿 ,张静乐 乐 ( 郑州大学 信息工程学院 ,...
基于Malt b的0—1包 问题 的动态 规划方 法求解 a背王 乐, 王世 卿, 张静 乐 ( 郑州大学 信息工程学院, 河南 郑州 405)502 摘要: 包问题 是 经熊 ...
动态规划0或1背包问题 8页 10财富值 基于Matlab的0_1背包问题的... 3页 ...[1 - 2] 法求解问题 ,首先要把实际问题抽象成数学模型 , 再进行相应的算法...
第3 9卷第 7期 210 2年 7月 计 算 机 科 学 Vo.9No713 . Coue Sinemptrcec Jl 02uy21 基于动态规划法求解动态01包 问题 —背贺 毅朝 田海燕 张新禄...
基于MATLAB的0—1背包问题... 3页 5财富值 基于Matlab的动态规划程序... ... 动态规划求解方法的Matlab实现及应用[1].txt爱情是艺术,结婚是技术,离婚是算术...
基于Matlab的0_1背包问题... 3页 1下载券喜欢此文档的还喜欢...一个会获得问题最优解的决策序列, 运用动态规划方 法的前提是所求解问题的最...
3页 1下载券 基于MATLAB的0—1背包问... 3页 2下载券喜欢此文档的还喜欢... 文章对动态规划问题的求解方法进行了分析研究 , 根据问题的特点 、 难点和关键...
第2 卷第1期92012年3月 经 济 数 学JOURLO NA FQUANITV CTTAIEEONOMCIS Vl2,o1o.9N.Mr2012a. 一种求解分组 0-1 背包问题的动态规划法蒋亚军1,易学军2 *...
实验3. 基于动态规划方法求解 0-1 背包问题 实验内容本实验要求基于算法设计与分析的一般过程(即待求解问题的描述、算法设计、算法 描述、算法正确性证明、算法分析...
决策过程 ,应用动态规划方法并且在计算机上通过MATLAB编程方便地求解资源分配问题.... 动态规划选址,背包matla... 2页 免费 动态规划求解方法的Matl... 26页 ...
热门文档