当前位置:首页 >> IT/计算机 >>

无限制背包问题的爬山算法_图文

第" 4卷 第 &期 " # # 3年 &月

小 型 微 型 计 算 机 系 统 CBU BU NU Z D ML WL 0 V BL

F " 4 NY * & EY } *" # # 3 G % }

无限制背包问题的爬山算法

,
( " ( $ 聂义勇 + ( " 储诚斌 $ 翔+ ( (
+ 中国科学院

沈阳自动化研究所 ( 辽宁 沈阳 + + # # + . 研究生院 ( 北京 + # # # $ / . 法国 特鲁瓦 + ( # # # / .

" 中国科学院

,

$ 特鲁瓦科技大学

,



要 !给 出 了 一 种 求 解 整 数 背 包 问 题 的 爬 山 解 法 ( 并对该算法的计算复杂度及最 坏 情 形 进 行 了 理 论 分 析* 通过与经 数值实验表明( 该算法简便易行( 在其 典的求解背包问题方法的对比研究 (给出了该算法的适用范围并展示其优越性 *

适用范围内具有计算复杂度低 (近优程度高等优点 * 关 键 词 !背包问题 ) 无限制 ) 爬山算法 中图分类号 !0 文献标识码 ! $ # + 1 2

文 章 编 号! + # # # % + " " # , " # # 3 . # & % + $ 4 " % # 3

56 7 7 8 7 6 9: 6 ; <= 7 < > ? 6 @ A 9B > ?C ; D > ; E @ ? F 6 ; @ G; F H E F D IJ ? > : 7 K 9
L MNO P Q R S T
+ " $ + ( " ( $

% % NU VWQ X Y S T Z [\ Z ] ^ S T _ Q S

+ ( "

$

, ( * * ( + # # + ( . ‘ a b c d e c fg c h i j i k i b l mnk i l oe i j l c p n* ‘ ‘ a b c d e c f+ p a j c e , ( * * ( # # # $ / ( . ‘ q a l l r l ms t e u k e i b p n* ‘ v b j w j c f+ p a j c e , ( + # # # /{ . xc j y b t h j i dl mz b q a c l r l f dl mz t l d b h z t l d b h t e c q b

! *0 = : E @ ? F D @ 2S ^ |] Q } } ~ } Q !_ Q S TR } T Y " Q # ] !$ Y " # ] ^% S ~ Y S & # " R Q S # ’ S R ( & R ~ ’( " Y _ } ^ ! |R & ( " ^ & ^ S # ^ ) ] ^~ Y !( } ^ * Q # XR S )# ] ^ % *, (# |Y " & # ~ R & ^~ Y S ) Q # Q Y SY $# ] Q &S ^ |R } T Y " Q # ] ! |^ " ^R S R } X + ^ ) X# ] ^~ Y !( R " Q & Y S|Q # ]& Y !^~ } R & & Q ~ R }R } T Y " Q # ] !& ] ^ R ( ( } Q ~ R # Q Y S& ~ Y ( ^Q &T Q ^ SR S )# ] ^& % ( ^ " Q Y " Q # XQ &) Q & ( } R X ^ )R _ Y % ## ] Q &R } T Y " Q # ] !*U #] R &_ ^ ^ S& ] Y |S Q SS % !^ " Q ~ R } ^ * ( ^ " Q !^ S # &# ] R # # ] ^S ^ |R } T Y " Q # ] !Q &^ R & X# YQ !( } ^ !^ S # R S )] R &# ] ^Q " # % ^Y $ } Y |~ Y !( % # R # Q Y S R } ~ Y !( } ^ * Q # XR S )] Q T ] * R ( ( " Y * Q !R # ^Y ( # Q !Q + R # Q Y S) ^ T " ^ ^|Q # ] Q SQ # &R ( ( } Q ~ R _ } ^& ~ Y ( ^ ! ) GK ./ > ? 0 E ’ S R ( & R ~ ’( " Y _ } ^ !) % S ~ Y S & # " R Q S ^ ) ] Q } } ~ } Q !_ Q S T!^ # ] Y )

1 引



解决 整 数 背 包 问 题 的 爬 山 算 法( 目的在于通过与各种经典算 法 的 比 较( 找到各类算法的不足之处( 并尽可能的弥补 不 足( 使这一研究领域更加完善 *

我 们 是 以 整 数 背 包 问 题 作 为 研 究 对 象 的( 其文字描述如 下! 设 有 c种 货 物 ( 分 别 为 第 w种 货 物 ( 2+ ( " ( 3( ( w与 q w e w c 给定待装载的总容积能力 4 要求确定 的 容积和价值* , 5# . ( 4 装 载 方 案 (使 所 装 货 物 价 值 之 和 达 到 最 大 *设 装 入 第 w 种货 物6 件 则需求解如下问题 ( ! w
c

= 理论分析
" < 爬 山 算 法 是 人 工 智 能 中 的 一 种 启 发 式 搜 索 方 法; 为了 (

我们先给出一系列相关 介绍 这 种 方 法 在 背 包 问 题 中 的 应 用( 概念 * 在背包问题中( 我们以装入货物的背包作为节点 * 其剩 ( 作为节点状态( 记为 u 相邻节点可以通 余容积 u , # 9u 94 . ( 6 过在背包中不断装入货物一个一个地产生出来 * 这样 ( 背包 问 如 图 +所 示 . 把这种描述问题的 题可以用一个有向 图 表 示 , * 有向图称为状态空间图* 可以看出( 图中的初始节点 ‘ #对应 其节点状态为 4 目标节点 ‘ 着 原 始 的 背 包( ( f对应着背包无 法再装入任何其他货物情况下的状态 * 图中的一条边 , 即相 邻 两 个节点的连线. 就对应着背包装入某一货物 h >?2 @ + ( " ( 的 过 程 其 路 径 价 值 为 所 装 入 货 物 的 价 值 则 背 包 问 3( A ( * h c q 寻找通向目 题的 求 解 其 实 就 是 从 该 有 向 图 的 初 始 节 点 出 发( 标节 点 的 一 条 最 优 路 径( 使得从初始节点到目标节点的路径 价值最大 *

28q * w w !R *7 6
w 2+ c

8e * * 94 w w h i 6
w 2+

, + .

: #为整数 ( 2+ ( " ( 3( w 6 w c 整数背包问题 , 因 其 对 每 类货物数量 6 + . w无 限 制 又 可 以 叫做无限制背包问题, 它是 ( % S ~ Y S & # " R Q S # ’ S R ( & R ~ ’( " Y _ } ^ !. 求解某些复杂的优 化 问 题 , 如下料问题. 的 子 问 题( 其算法的 微小改进都可导致可观的效果 ( 具有一定研究价值 * 整数背包问题可以看作 # 许多 % +背 包 问 题 的 特 殊 形 式 * 求解 # 背 包 问 题 的 方 法 都 可 以 应 用 到 整 数 背 包 的 求 解 中 % + ; + ( 4 < ; + < ; + ( < 来* 经典的算法有动态 规 划 分支定界 ( 贪婪算法 不 ( (
$ < + < 这些方法计算复杂度不同 完全枚举法 ; 和其他近似解法; * (

解的效果也大不相同 ( 因此适用的情况也不一样 * 本文提出 的

收稿日期 ! 宋 翔( 博士研究生 ( 研究方向为应用数学及计算机辅助工程 ) 聂义勇 ( 研究员( 博士生导师( 研究方向为应 " # # $ % # & % " ’ 作者简介 ! 用数学及计算机辅助工程 ) 储诚斌 ( 法国特鲁瓦大学教授 ( 博士生导师 ( 研究方向为工业优化及系统调度 *

万方数据

s期



无限制背包问题的爬山算法 翔 等7

# j r j

在 状 态 图 中 寻 找 目 标 或 路 径 的 基 本 方 法 是 搜 索! 对于状 态图的搜索 ! 已经提出了许多策略 ! 它们大体可分为盲目搜 索 和 启发式搜索两大类" 爬山算法就是一种具有不可回溯性的

则计算装入货物 d 的可能价值 8 如果 N f: ! = =# ! D ! e! < ! d d [ 否则 8 ?@ 9 R < ! =C " d d d F : N 步骤 D 求出货物 使得 8 如果 8 则将 " ! =-) L Q ! gC ! E d E E I 8
d JK

货物 E 装入背包 :中 " 置 ‘=‘h L 且F Q ! ! =: R " b=F b?F E E E : N 转入步骤 # " 在步骤 D中的启发函数 @ 采用 @ 则计算复杂度 9 < 9 < ! # A : : D j 采 用 则 计 算 复 杂 度 为 其中 i 为 Z ! 9 < ! 9 P[ < ! 9 P[< D A @ : Z i i c 为 背 包 c中 所 能 装 下 货 物 的 最 多 件 数 ! 以下 = -) L M O Q ! I H JK N H 同" 下面给出两个爬山算法的最坏情形分析 " 性质 # " 9 < f@ 9 < # A D A @ : : 证明 7 如果 : 显然有 @ 结论成立 " VN ! 9 < =@ 9 < =C ! A # A D A : :
U k k k! 否则必存在 H 使得 : 且 @ 9 ! = -) AT N H #9 A< H J K< : I H JK

图 # 背包问题的状态空间图 " # ’ $ % & ( ) ( *+ % ) & , ) -. / ,0 1 ) 2 3 ) 4 02 , / 5 6 * 启发式搜索方法! 其基本思想是7 当扩展一个节点时! 采用估 计 算 每 一 个 子 节 点 ;的 估 价 价 函数 8 < => 9 < ?@ 9 < 9 ; ; ; : : : 值! 并选择估价值最大的子节点作为下一个要考察的节点 ! 废 为从初始节点 B 其中 > 弃所有其 他 子 节 点 " < 9 A C 到 节 点 A的 : 路 径代价! 如图一中节点 B 有> 是从节 ! 9 =F ?F ! 9 < D E< G H A : @ :
D

: : A A k! 则 L M O PF Q =M k O PF H H N N H H k R N : A H k ?M kf 9 < =F O PF # A H H @ : k N H k : R N A H k ?-) L O PF Q = H H IM F H JK N H k ?@ k< 9 R f H # A H F : N L ?@ 9 R < S TN Q = H # A H A H F : N : -) I
H JK

9 < D A @ : 命题得证 " 性质 D 对于背包问题 \ 设采用爬山算法得到近似解 m " ! l n n n n n n 则有 =9 ! ! e! < " # <F 9 R f]^ 9 <p D <F # D o H ?@ # H< H? H H H c N _# \
# # # n< 9 R f]^ 9 < " D H c N _D \ @ # 证明 7 我们首先证明结论 # 给定正整数 E 因为 < ! ! # fE fo ! E R # G =# o G =E E R # U n n 根据性质 #的证明 ! 可以得到 qN R TqN TN ! H H c G G

是启发式函数! 点 A到 目 标 节 点 B > 的最优路径的估计代价! 其形 式 通 常 需 要 我 们 根 据 问 题 的 具 体 特 性 进 行 设 计" 在本文 中! 我们给出两个计算复杂度较低的启发函数的形式 7 : A 9 < =-) L M O PF Q ! # A G @ : I G JK N G I L F ?@ 9 : R N < S : TN Q ! : TN H # A H A H A X-) H JK U 9 < =W D A : @ C ! : VN Y A
U

qN< 9 R f # @ c
n H G =# G E R # H JK G =# E R # G =# nR < nTN qN qN L ?@ 9 R R Q = H # H H S H H F c c -) I GN G E R # n?@ nRH n< qN 9 R = H # H F c E GN E G =# E n n qN ?@ 9 R < H # H F c E G G =# E R # n! 不等式两边同时加上 q F 得到 H G =# G E R # E R # E R # E

根据算法 < 9

其 中M 表 示 不 大 于 实 数 N的 最 大 整 数 ! 以 O = -% L Q ! H N N 1 N
U H JK

下 同" 可以简化计算为 由于爬山算法具有不可回溯性! < 9 A > : 同时 从节点 A的 父 节 点 到 节 点 A的 路 径 代 价 ! 如> < =F " 9 E H : D 由于 爬 山 算 法 是 一 种 启 发 式 搜 索 策 略! 往往不能够得到全局 最 优 解! 所包含的信息量大小决定 其采用的启发函数 @ < 9 A : 了搜索性能的好坏 " 和@ 的 计 算 复 杂 度 分 别 为 Z9 本文给出的 @ 9 < 9 < < # A D A : : [ D 和Z 而 他 们 所 包 含 的 信 息 量 也 不 一 样 我 们 分 别 以 这 两 9 ! " [< 个函数作为启发函数构造出来两个爬山算法具有不同的计算 复杂度和搜索性能" 我 们 将 这 两 种 算 法 求 解 背 包 问 题 \所 得 到的目标函数值分别记为 ]^ 和 ]^ 下面分别 9 < 9 < " _# \ _D \ 给出算法步骤和最坏情形分析 " 算法的具体步骤如下 7 初始 化" 令 ‘= a! 令F ! F b= C b ‘代 表 装 入 货 物 的 集 合" 代表装入货物的总价值 ! 令: =c ! :代表节点状态 " 步骤 # 退出! 否 则 对 于 每 个 货 物 d9 "如 果 : V-% L Q ! 1 N d d
d JK

n n n n n q q q 9 R fqF 9 R = H?@ # H< H?F H?@ # H< c c F N N E G =# G G =# G G =# G G =# G E E n n q q 9 R H?@ # H< c F N G =# G G =# G o G =# G U o G =# G nV ! 9R n< 又知道 ! 所以有 qN R ! H # cq N H =C c N@ D G =# D G =#

n?@ n< n?@ n< qN 9 R fqF 9 R fef H # H H # H F c N c G G G G o R # G =# o R # G =# o G =# n n n qF qN ?@ 9 R < fqF =]^ 9 < H # H H c _# \ G G G

结论 # 得证 " 对于结论 D 也可以证明 < < !
E R # n< qN 9 R = D H @ c G G =# E R # H JK G =# E R # G =# n n qN qN L ?@ 9 R < S R Q f F c N c -) I H # HR H HTN H G G

万方数据

1 M w ^
0 . 1 $ %& 2 31 0 . 1 2 31



















+ V V ^年
?. ? . 4 4 $ 1 $ + ?3 Y( $ 0 ? 4 $ 0

5. 6 584 /4 /4 ’ )* , . . 9 3 $ + $ $ 7 $ $ !" # ( 24 2 0 . 1 5)*,. 5.56 3 $ + -/ 4 $ $ ( 0 24 0 2 31 0 5 5 /4 , . $)* + $6 ( 0 2 2 31

性质 1 , 6

? )( ?) $ $ ( 1 +

根据算法 6 ,

?. ? . 4 4 $ 1 $ + ? )( ? )W ?) X Y( $ $ $ ( 1 + 0 ? 4 $ 0 ?. ? ?. ? . 4 4 . 4 4 $ $ 1 $ + 1 $ + ? , ? . W ? X 6 Y( $ 0 4 4 $ $ 0 0 根据引理 + 有 : ? 4 ? . 4 $. $ 1 + ? ? ? X Y( , 6 ; $ )( $ )W $EFG ( H+ = 1 + 0 ? 4 $ 0 因此可以得到 : ?. ? ?. ? . 4 4 . 4 4 $ $ 1 $ + 1 $ + ? 6 EFG , 6 ), ? . W ? X 6 Y( $] I J K, = H+ = 0 4 4 $ $ 0 0 ? , 6 )( $ FG H+ = 0

再由结论 1 的证明过程 : 同理可证结论 + 6 6 ; ? ? ? 引理 < 对于背包问题 = 设存在最优解 > ; : 3, : : @: 1 + $ $ ? 5 5 B 5 采用爬山算法得到近似解 > 则有D 若A 6 : : : @: 6 ; 1 6 3, A 1 + C $ $ $ $ 则 FG 若A 则 FG E+ : , 6 3I 6 L + 6 EM : , 6 3I H1 = J K, = H+ = J K , 6 ; = 证明 ; 我们只证 明 结 论 + 结论 1 同 理 可 证; 由A 6 : 6 E M及 性质 + 有 :
5 )* 56 , 6 8( , . 3 $ + $ FG H+ = 4 1 1

’ )* , . 6 7 84 9 3 $ + $ $ !" # ( 4 $ %&

根据算法 6 ,

显然

)!" # ’ ( )* , . 4 . 4 6 7 . 4 84 9 7 . 4 84 $ 2 1 $ 2 $ 2 $ Q( T 2 %& N !" # P S3 $ %& 7 4 O. 4 8V R( U $ $
N

?. ? . 4 4 $ 1 $ + 故 W ? X 81 : 4 $ 0

? )( ? )( ?EFG 从而 , 6 : $ $ $ ( H+ = 1 + 0 ?E $ ( 0

. 4 . 4 $ 2 Q( T )!" # ’ ( )!" # ’ W X Y( 9 7 . 4 84 9 7 . 4 84 $ 2 0 $ 2 $ 2 %& 0 %& N 3 4 0 !" # P S $ %& R( U 7 4 O. 4 8V $ $
N

1 , 6 ; FG H+ = M

2 : $ : 0 %& A

!" #



( )( )Z Y( 7 4 )4 )Z Y4 E2 $ 0 0 2 $ 0 0 ( 7 4 O. 4 8V $ $
N

9

. 4 . 4 $ 2 记Z 8, 3W X 6 0 4 0

1 ^ 所以 I 6 ] FG , 6 ) , 6 3 J K, = H+ = FG H+ = FG H+ M M FG H+ , = 6 M 结论 成立 O : + 6 ; , 6 ; = I J K, = 6 ^

‘ 算法比较
背 包 问 题 的 研 究 方 法 已 经 很 多: 为了比较本算法的适用 范围: 我们用经典的三个算法与本文给出的两个爬山算法进 行比较 ; 这三个经典算法分别为动态规划 : 贪婪算法和两个 近
M X 似 解 法: 其中统计近似解法 1 不 完 全 枚 举 法W 作了排序方 , 6 面的修正 : 使得它适合于求解无约束背包问题 ; 表 1给出 了 几

? / 6 ; $3I ( J K, = 2 31 2

同时 : 又有 FG 所 以 FG , 6 EI 6 : , 6 3I H+ = J K, = H+ = J K 结论 + 得证 ; , 6 ; 6 = 引理 [ 设采用爬山算法得到近似解 B ;对 于 背 包 问 题 = : > 5 5 5 则 有 : : @: 6 : 1 6 \2 : %&: )Z Y4 E: ( )Z Y( 3, 1 + C 2 C C 2 C C $ $ C 4 $ 有( EFG , 6 L + 6 \2 : : %&: )4 )Z Y4 E: )( )Z 2 $ C C 2 $ C H1 = $ C 4 此处 Z 为整数 ; Y( EFG , 6; OV , %&6 C C H+ = C 证明 ; 由引理 1的证明过程 : 直接可以得到 , 6 8 !" FG H+ = #
2 : $ : C %&

种算法的计算复杂度和近似比 ; 表 1 几种背包问题的求解算法比较



( )( )Z Y( 7 4 )4 )Z Y4 ]2 $ C C 2 $ C C 7 4 O. 4 8V ( $ $
N

9

a " b c d1 e f !g " h i j f k" !f k lj d m d h " c " c l f h i n o !j p f hq k " g j " r qg h f b c d !
计算复杂度 动态规划 贪婪算法
W M X 近似解法 1 W 1 X 近似解法 +

8

2 : $ : C %&

)( )Z Y( 7 )4 )Z Y4 E9 2 $ C C 2 $ C C !" #’ ( 4

近似比 1 1 v + N + v M + v M M v ^

引理结论 + 得证 ; 同理可证结论 1 6 6 ; 定理 1 给 定 背 包 问 题 的 任 何 例 子= 令I 表示问 ; : 6 J K, = FG H1 , = 6 + 题 =的最优 目 标 函 数 值 : 我们有近似比 1 6 O L + 6 I J K, = 6 M FG H+ , = 6 M O ; I J K, = 6 ^ 证明 ; 我们只证明结论 + 结论 1 同理可证 ; 6 : 6 ? ? ? ? 设 最优解 > 其中 A 件货物已经按 3, : : @: 6 : , E_ 6 ; 1 + A $ $ $ A ? ? ? 照它们的价值进行排序 ; 即令 ( $ 8( $ 8@8( $;
1 + A

, 6 I u 6 , u I u c f l + , 6 I u c f l u +
M 6 , + Yu I + , Yu 6 I _ M , Yu 6 I _

se t1 se t+

从 表 1可 以 看 出 : 动 态 规 划 适 用 于 背 包 容 积 -较 小 的 情 况: 不完全枚举解法和贪婪算法由于其具有较低的计算复杂 度: 可以作为一个子程序在求解其它复杂问题近似算法中反
^ X 当背包较大 对计算精度要求较高时 可以根据情 复 应 用W ; : : 况采用不同的启发式解法; 数值实验和理论分析都可以看出

若 A 则根据引理 1 结论 + 自 EM : : , 6 3I 6 : 6 FG H+ = J K, = 下设 A 然成立 ; OM ;
? ? ( ( $ $ 0 2 3!" ’ ?7 3M : ^ : @: 9 ; # 2 A ? 4 4 $ $ 0 2 由算法的路径搜索 : 我们有

设货物 0 使得

近 似 解 法 +和 FG 而 FG H1的 性 能 相 近 : H1的 计 算 复 杂 度 在_ 的 情 况 下 低 于 近 似 解 法 ]+ Yu + ; FG H+的 计 算 复 杂 度 虽然较高 : 但从数值实验可以看出它的解近优程度最高 : 而其
+ 复杂度与动态规划相比在 情况下也有一定的优势; O_ Yu 因此可以根据具体问题 : 选择不同的算法 : 尽可能以较低的 代

6 3 / (3( )( ) / (E I J K, =
? $ 2 31 2 ? $ 1 ? $ + ? $ 2 3M 2

万方数据
A

A

E期 价满足计算精度要求 !



翔 等V 无限制背包问题的爬山算法

8 9 ; ;

理论论证和数值实验表明H 该算法的计算复杂度与背包问题 没有 直 接 的 联 系! 弥补 的 规 模 =关 系 较 大 而 与 背 包 的 大 小 F 了动态规划方法的一些不足 ! 同时我们对这一算法的性能和计算复杂度与几种求解背 包问题的经典方法进行了对比实验 H 结果表明 H 本文提出的 爬 山算法是求解背包问题的有效方法 !
< # ? 8 ?

" 数值实验
为了比较各种算法在计算性能上的差异! 我们做随机数 表 # 数值实验结果 $ % & ’ (# ) ( * + ’ , *. / + 0( 1 2 3 % ’ ( 4 5 ( 1 2 0( / , *
! 67 = > 动态规划 计 算 结 果 8 ; ; # ; 8 ? 9 8 ? ; : 8 ? 8 ? ; # ? ;

V O P Q P R P S T P U
8 A [ H] [ !A I ! @W X Y Z 2 5 2 / \ ^ Y / \ & ( / 05 + , ( 10% , Z ( 0% , 2 3 * BJ V H # ? ? 8 ! _ ( 2 ‘ 2 / \ a 3 2 ( / 3 (b 1 ( * * # c [ ! d eX a Z 2 f + d / , 1 g + 3 , 2 /, -% 1 , 2 . 2 3 2 % ’2 / , ( ’ ’ 2 \ ( / 3 ($ ( 3 Z / 2 h + ( I !] Vb H BJ 2 i % / 1 ( * *.] 2 i % /W ’ ( 3 , 1 / 2 3$ ( 3 Z / ’ \ f^/ 2 j ( 1 * 2 , f # ? ? # ! 9 Xd [ H H ! W k2 k/ \ l ^dl % / \ a mXl ] 2 % / \ n + / g % , 2 /. 12 / , ( \ ( 1 I ! V XH 5 1 \ 1 % 002 / \ BJ a Z ( / f % / \ 1 , Z ( % * , ( 1 / ^/ 2 j ( 1 * 2 , fb 1 ( * * # ? ? 8 ! : e/ Ha !$ g 1 ( %c g 2 2 ’ j % / - B% 1 , ( ’ ’ o- g 2 0( / * 2 / % ’5 % 3 p 2 / \ V %* J !W 5 1 & ’ ( 0* + 1 j ( fI q + 1 5 ( % /q + 1 / % ’. m5 ( 1 % , 2 / % ’ Hr!8 : 8 H # ? ? # V # : 8 [ # ; # ! ) ( * ( % 1 3 Z ; l Hl !$ 2 ’ 01 (b A 01 f) W Z (, Z ( 1 f% / g3 05 + , % , 2 /. J ! m5 : H8 C < < V8 ? : ; [ p / % 5 * % 3 p. + / 3 , 2 /I q ( 1 % , 2 / *) ( * ( % 1 3 Z8 8 ? E : !

9 C : 9 ! D9 C < E ! #9 C C 9 ! ?9 C C D ! E9 C C C ! ; : ? ? ?

贪婪算法 9 < 8 C ! C9 < < ? ! D9 ; C : ! E9 E 8 < ! E9 < ? ? ! 89 E C 8 ! C 近似解法 8 9 E E : ! C9 D D ; ! 89 C 9 ; ! 89 C # : ! ?9 C 9 8 ! 99 C : ; ! : 近似解法 # 9 C 9 < ! <9 C ; < ! :9 C D D ! 99 C C 8 ! ?9 C C D ! ;9 C C D ! < @A B8 @A B# 9 C 9 < ! D9 C < : ! #9 C D < ! 99 C C : ! ?9 C C E ! 89 C C D ! D 9 C : 9 ! D9 C < < ! <9 C C 9 ! ?9 C C D ! :9 C C C ! ;9 C C C ! C

F 值 实 验! 令F 按照I 的分布随机生成货物 G: ? ? ? H I J H # ? ? ? J > 体积 K 其中 I 表示 不 小 于 实 数 K的 最 小 整 数 ! 并令货物的 H J L K 价 值 与 它 的 体 积 相 同H 即M 以 方 便 比 较 由 于 研究的问 GK H ! L L 所以不考虑每类货物的数量限制 ! 对给 题为无限制背包问题 H 定 的货物种类 =和给定的 > 随机生成 # 表 #给出了 ?个例子 ! H 每组随机数值实验结果的平均值 !

附中文参考文献 V
徐宗本 ! 计算机数学 I 北京 V 科学出版社 H 8 陈志平 H ! # ? ? 8 ! BJ 人工智能技术导论I 西 安V 西安电子科技大学出版 ! # 廉师友 ! BJ 社H # ? ? # ! 贵刚H 宋翔! 整数规划基础I 沈 阳V 东 北 大 学 出 版 社H ! 9 聂义勇H BJ # ? ? 8 !

N 结



动 态 规 划 方 法 是 求 解 背 包 问 题 的 一 个 经 典 方 法H 然而在 实际 应 用 中 会 受 相 关 参 数 取 值 较 大 影 响H 使计算时间和空间 令人难以忍受 H 因此本文给出了无约束背包问题的爬山解 法 H

万方数据


相关文章:
无限制背包问题的爬山算法_图文.pdf
无限制背包问题的爬山算法 - 给出了一种求解整数背包问题的爬山解法(并对该算法的
无限制背包问题的爬山算法.pdf
无限制背包问题的爬山算法 - 给出了一种求解整数背包问题的爬山解法,并对该算法的
解决01背包问题算法比较_图文.ppt
解决01背包问题算法比较_IT/计算机_专业资料。分别使用动态规划法,贪婪算法,回溯法,分枝定界法等四个算法对...
山西证券-101227-2011年汽车行业投资策略-量变减缓、质....pdf
6页 2财富值 无限制背包问题的爬山算法 4页 2财富值如要投诉违规内容,请到百
背包问题的贪心算法_图文.ppt
4.2背包问题的贪心算法 4.2背包问题的贪心算法 0-1背包问题: 背包问题:
0-1背包问题算法_图文.ppt
0-1背包问题算法_IT/计算机_专业资料。0-1背包问题 2011-11-18
求解多背包问题的人工鱼群算法_图文.pdf
求解多背包问题的人工鱼群算法_哲学/历史_人文社科_专业资料 暂无评价|0人阅读|0次下载 | 举报文档 求解多背包问题的人工鱼群算法_哲学/历史_人文社科_专业资料...
完全背包问题_图文.ppt
完全背包问题 (无限背包)主讲人:山成虎 1 问题 2...二维数组】【算法分析
第3章-背包问题_图文.ppt
若物品装入到背包中时,背包有多个限制 就称为多维...常用的背包问题经典求解技术(不含启发式算法) 主要...
0/1背包问题的量子算法_图文.pdf
维普资讯 http://www.cqvip.com 软件 时空 文章 编号:0807(061230 105020)2307-2 01/ 背包问题的量子算法 AQunuAIoimoRslete01kasc olm atm grht ...
0-1背包问题的一种新的启发式算法_图文.pdf
(2006)04.0301.03 空军雷达学院学报JournalofAirForceRadarAcademy V01.20No.4Dec.2006 O一1背包问题的一种新的启发式算法谈群1,夏敏学2,钱建刚3,彭3.空军...
背包问题的二分网格算法_图文.pdf
维普资讯 http://www.cqvip.com 计算机 科学 20V13M. 05o.226 背包问题的...无限的 ,品i物 的容量和效益分别 的一个多项式算法 , 但遗憾的是 , 该算法...
数学建模 - 第七章 背包问题_图文.ppt
§3 背包问题的近似算法 有改进的吗? §3 背包问题的近似算法通过前面介绍的
Pascal经典算法-背包问题析_图文.ppt
经典算法问题解析---背包问题 前言背包问题是程序设计中一个很经典的 问题,很多
0-1背包问题算法分析与研究_图文.pdf
我们对此问题的进行一般描述如下: 一个登山者想要选择不同的物品装满他的背包。...分别为优化算法和近似算法的价值,它 们限制在fn(2k--1))/pmax的数量内。...
背包问题_图文.ppt
贪心算法 ? 有一个背包,背包容量是M=150 背包问题徐杰 背包问题问题描述:给定...完全背包:而现在完全背包的特点恰是每种物品可选无限件,所 以在考虑“加选一...
求解多重二次背包问题的改进遗传算法_图文.doc
龙源期刊网 http://www.qikan.com.cn 求解多重二次背包问题的改进遗传算法 作者:刘梦佳 向凤红 毛剑琳 郭宁 来源:《软件导刊》2018 年第 01 期 摘要: 多...
0_1背包问题的蜂群优化算法_图文.pdf
0_1背包问题的蜂群优化算法_理学_高等教育_教育专区 暂无评价|0人阅读|0次下载 | 举报文档 0_1背包问题的蜂群优化算法_理学_高等教育_教育专区。0_1背包问题...
背包问题(贪心算法).doc
算法分析与设计实验报告 第 4 次实验姓名 时间 实验名称 11.14 下午 学号 地点 四合院 班级 贪心算法实验(求解背包问题) 1.通过上机实验,要求掌握贪心算法的问题...
Pascal经典算法-背包问题析_图文.ppt
经典算法问题解析---背包问题 前言背包问题是程序设计中一个很经典的 问题,很多题目都是在该问题上延伸开来的, 对与背包问题我们有多种解题方法(算法), 其中最...