文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 自然科学 > 数学 > 基于MATLAB的0—1背包问题的动态规划方法求解 DP算法 分治法 递归法 NP难题
侵权投诉

基于MATLAB的0—1背包问题的动态规划方法求解 DP算法 分治法 递归法 NP难题

0-1背包的规划问题

维普资讯 doc.guandang.net

第 4期

王

乐等:基于 Mal的 0背包问题的动态规划方法求解 tb a一l {

8 9

都把所有于题的解存于该数组中。对于重复出现的子问题,只有在第一次遇到时才给预求解,并把其答案存放在该数组中保存起来,以便再遇到时可直接引用而不必重 新求解,『可解决所对应的子问题树中的子问题呈现大因n

fr o w=0t w)v 0W 0 o[,;

/将二维数组第一行赋值全零/ fr f= 1r n o i { ) ) fr( o W=0 t oW )

量重复的问题。

i w. w) f(≤

V[,] ̄ ( i,] i=na V[—lw, w x+( i, V【—lw—w], )

3解决背包问题的 D P算法 3 1求解过程描述 .

/ v w纪录权值至少为 w且值最大的:集 I,,,:/ ]产 12… n ee l s

假定 w>0且两个正整数数组分别为:,2…,, ( V, 一

V[, i w卜 v[一1w; i,] R t v[,; er u n i W] }

旦.

)和 (l他,他 )望找到∑ t’最大且趾l …, ,期,2 ,一 i l 一

∑他≤ W的子集为T∈{,,,。, 12…, l !采用上述动态 规划思想,

决背包问题的求解过程可描述如下:解

另外再定义一数组 ke[,纪录所选择的物品。当 e i p K] 第个物品选中时,将其赋值为 1否则为 0,。 K=W

步骤一:将问题分解为小的子问题。 构造一个二维数组 v o,…w][… 0 1≤≤ n且 0≤叫≤ W

fr(=nd wno1 o i o t )

I (epi= 1 f ke[, ) K] { o t u; u p ti

V i础][,用来存储权值至少为础且值最大的子集 T ∈{,,,} l2…

K=K~w[ i] J丁∈ J下∈

即:[础=Hx∑: ] l{,, a T∈{ 2…,, 1, i∑,} ≤础}

输出的值即为所选择物品对应的编号。 3.测试结果 3

计算出所有满足条件的此二维数组的值, V[ 则,

]就包含解决问题的解决方案。 步骤二:根据子问题的解递归定义最优解的值。 设置初始状态集合:

在 Ma a6 5 tb,E l 环境下对该算法进行测试的过程和结 果如下:

v[,=0当 0 o础]≤≤ W,没有任何项目时

>> v 1 0 05]w=[ 3;=4w=1;=[O4 0; 3 5 6]n; 4 0 >>[ o t= npak vw nw) V,u] K aSc (,,, V=

V[,=一o < 0 i础] o当, 递归步:

非法

0 0 00 1 0 1 0 1 0 0 1 0 1 0 1

[础] T x V[一1础]+( i,一 =i ( i,, i a, V[—l础 硼,中1 i 其≤≤,≤础≤ W_。 0 3 J

0 O0 4 0 4 0 4 0 5 0 4 04 0 5 0 0 0 00 0 4 04 07 04 0 5 0 005 0 5 05 09 0 0 5 0 5 0 5 09 O t 0 2 04 U=

式中: i,为上一轮中重量为"时所求得的 V[一1础] t 3 3价值最大值;i V[一1 W一"] V+( i, L表示: O 选取 'i W时的价值为 7, d此时允许的最大的重量为,一是还剩下 的可承重量。

数组 Ot U输出的 i值表示物品的编号。结果表明选择 第二和第四种物品,所得到的最大价值为 9。 0此算法的时间复杂度为 O( w )。[ 引

一

V[,

] i 的取值为[一1训]"+( i,,和0 i V[一1 埘,中的较大值。]如果有种物品可以选择,而此时所能 ①不选新加入的第种物品。此时只有一1种物品,

承受的最大重量为训时,只有两种选择: 最大承受重量为吐的最大价值为 V[一1], i,。

4与其他方法的比较与分析 一

般来说,用来解决背包问题的方法主要有递归法和

贪心法等,但用这两种方法来解决背包问题都有其不可避 免的缺点。递归法虽能遍历搜索空间,找到最优解, 但由于此问题的解的空问是以级增长的,所以它只适用于解决

②选择新加入的第 i种物品。 i第种物品的重量为, 的价值为,现所能承受的最大重量为他一础;,而 l 种物品还可以选择,时的最大价值为[一1一此 ,

小规模的背包问题;而贪心法又很难真正找到最优解,即 使能找出较优的解也往往与真正的最优解相差很远。如果采用自顶向下的分治法解决此问题,将会随着物品的增多以级规模指数递增,囡为分治法要重复计算相同的值。 但采用动态规划算法,则川解决重复计算相同内容的问题,以达到减少冗余的根本目的。由于采用的动态规划实质上是一种以空间换时间的技术方法,此在实现过程因 (转第 9下 2页)

因此价值最大值为( 7+V[一1础一础]。 d i,『) 步骤三:自底向上进行计算 V[ M] 。底: 0] 当 0叫≤ W; v[,=O≤ 自底向上计算:使用公式 V[, i硼]=n x V[一1 l( f, a u]+( i,,, V[一1 3 2实现算法。 K aS c(, nw ) np akvw,,

u]。,)

基于MATLAB的0—1背包问题的动态规划方法求解 DP算法 分治法 递归法 NP难题

上一页第2页

你可能喜欢

  • matlab动态规划
  • 背包问题
  • 动态问题
  • 动态规划问题
  • 蚁群算法
  • 背包算法
  • 装箱问题
  • MATLAB线性规划

热门文档

相关文档

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

    2006 基于 Matlab 的 0- 1 背包问题的动态规划方法求解王 乐, 王世卿, 张...关键词: 0- 1 背包问题; DP 算法; 分治法; 递归法; NP 难问题; Matlab ...

  • 【论文】基于动态规划法求解动态0-1背包问题

    在动态规划法基础上,提出了一种求解背包载重随机变化的RTVKP问题的确定性算法,分析了其复杂度和成功求解需要满足的条件。对两个大规模实例的计算表明,该算法是求解...

  • 实验3. 基于动态规划方法求解0-1背包问题

    算法 描述、算法正确性证明、算法分析、算法实现与测试) ,在针对 0-1 背包问题求解的实践中 理解动态规划 (Dynamic Programming, DP) 方法的思想、求解策略及步骤...

  • 解0-1背包问题的动态规划算法

    2、求解问题的动态规划原理与算法 2.1动态规划原理的描述 求解问题的动态规划有向前处理法向后处理法两种,这里使用向前处理法求解 0/1背包问题。对于0/1背包问题...

  • 求解0-1背包问题算法综述

    2 2.1 求解 0-1 背包问题的常用算法动态规划法 ...是美国 0-1 背包问题是一个 NP 难题, 它在很多...本 文利用 MATLAB 软件中的 SORTROWS 函数进行排序 ...

  • 动态规划0—1背包问题

    动态规划0—1背包问题_计算机软件及应用_IT/计算机_专业资料 暂无评价0人阅读0次下载举报文档 动态规划0—1背包问题_计算机软件及应用_IT/计算机_专业资料。 ...

  • 动态规划(dp算法)

    递归策略 在例 3 - 4 中已建立了背包问题的动态规划递归方程,求解递归式( 1 5 - 2)的一个很自然 的方法便是使用程序 1 5 - 1 中的递归算法。该模块...

  • 基于贪心策略的遗传算法求解0-1背包问题

    针对 0-1 背包问题的解法种类繁多,如贪心算法、动态规划、遗传算法等等。本 ...matlab 根据邻接矩阵作图... 4页 免费 遗传算法及其应用实例 20页 1下载券 第...

  • 动态规划-0-1背包

    递归定义最优值由前面的最优值过程分析实例,根据0-1背包问题的最 优子结构...思想动态规划算法与分治法类似,其基本思想也 是将待求解问题分解成若干个子问题...

  • 关于0_1背包问题的算法研究

    1 背包问题的算法研究李北斗 (中国地质大学信息工程学院 武汉 430074) 摘 0 /...但是动态规划算法有着自身的特点 , 解决了分治法中相同子问题重复求解的问题 。...

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