文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 工程科技 > 信息与通信 > 基于Matlab的0_1背包问题的动态规划方法求解
侵权投诉

基于Matlab的0_1背包问题的动态规划方法求解

第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 与其他方法的比较与分析

一般来说,用来解决背包问题的方法主要有递归法和贪心法等,但用这两种方法来解决背包问题都有其不可避免的缺点。递归法虽能遍历搜索空间,找到最优解,但由于此问题的解的空间是以级增长的,所以它只适用于解决小规模的背包问题;而贪心法又很难真正找到最优解,即使能找出较优的解也往往与真正的最优解相差很远。如果采用自顶向下的分治法解决此问题,将会随着物品的增多以级规模指数递增,因为分治法要重复计算相同的值。但采用动态规划算法,则可解决重复计算相同内容的问题,以达到减少冗余的根本目的。由于采用的动态规划实质上是一种以空间换时间的技术方法,因此在实现过程

下转第页)

上一页第2页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email