当前位置: 首页 > >

基于Visual c ++ 的0-1背包问题的贪婪算法_论文

发布时间:

维普资讯 http://www.cqvip.com 学 术 论 坛  基于 Viu lc+ 0 背包 问题 的贪婪算法  s a + 的 -1   杨 晓红  ( 中国移动广东公 司湛江分公司  5 4 0 ) 2 0 0  摘  要 :背包 问题 是 经典 的 NP 组 合优化 问题 之一 ,在 管 理 中的资 源分 配 、投资 决策 、装 载 问题等 领域 有着 广泛 的应 用 。文 中给  出0 1   背包 问题的数学模 型 ,然后 简单介绍 了贪婪 算法 ,并使用这这种 算法解决 0 背包问题 ,通过在 vu a C +6 0 境下对  —1 isl + . 环 算法 进 行测 试 和分 析 ,实 验结 果证 实 了所 提 出方 法的 有效 性 。   关键词 :0 背包问题  贪婪算法  贪婪准则  —1 中 图分类号 :  1  TP3    1 文 献 标 识 码 :A   文章编号 :10 — 8 22 0)5c 04  0  0 4 0 6 (o 70 () 15 2 背包 问题是 一个典型 的 N P问题 , 对该 问  ( ) 物 品按单位 价值  从大 到小排 序 。 2对   题 的求解 方法的研究 无论是在理 论上 , 还是 在  () 3 将排序 后的物 品依次 装入背 包。对于  实践中都具 有一定 的意义 , 如管理 中的资 源分  当前物 品 j, 背包剩余可 装重量大于或 等于  若 配 、投 资 决策 、装 载问题 等 均可建 模 为背 包  则将物品  装入背包 , 继续考虑下一个物品  问题 , 其解 法优劣 将直接影 响到运作效 率与成  i , +1 重复 步骤 3 否 则得到 问题 的解 , 出。 , 输   本 。因 此 , 年 来此 问题 被 广泛 研 究 。文 中 *   23 . 实现 算法  对 背包 问题 建 立数 学模 型 , 后提 出贪婪 算  然 # i c u <i sr a . n l de o t e m h>  法 。通过 在 vs a  + 6 0 i lc + . 环境 下对算 法进  u #d f e ma   0   / 最 多物 品数  ei   x 1 0 n / 行测试 和分析 , 出在 求解的 背包问题规模 比  得 v i  o t n   , o t ama 】 l a    od s r( t n f a  [ x , o t b i l f 较 大时 , 贪婪 算法 可 以得 到较 好结 果 。 用   【 x) ma ]   / /按单位 价值排 序排序  {   , fr = } = } +  o( 1i n i ) i < + cn i >>vi; [  ] c ut o <<e dl  n } C U <<”请 依次 输 入物 品的重 量 :” 0 t   <<e dl  n } fr = ; n i +  o( 1i i <= ;+ ) cn i>>w[ } i  】 c ut o <<e l  nd } 1问题描述  f r =1i n i +   o( } i <= }+ ) { i w【j / t J i  【= 】 /复制数组 w【到 t】 i [ J i   ki vij 【= 【   J 】 / /复制数组 vi ki 【到 [  J 】 i } J   =0 0 背包 问题 是指给 定件物 品和 一背  —1 包 , 品的重 量是 , 物 其价 值 为 , 背包 的容量 为 ,   求从 这件 物 品 中选 取一 部分 物 品且对 每件 物  品 , 么选 , 么不选 , 要 要 要求满 足被放入 背包的  物 品的总 重量 不超 过 背包 的容量 。 如果所 有  物 品的重 量之 和小于背包 的容量 , 显然此 时的  利益为 所有物 品的价值之 和 , 但在实 际问题一  般是 背包的容量 小于物 品的重量之 和 , 就要  这 求选 取适 当 的背包 放入 使 得利益 最 大化且 物  品 的总 重 量不 超 过 背包 容 量 。   数 学 模 型 为 : ”Xs   己 I L i i l   it jh,   n  , k; f a  l t ,3 cma 】 l t t ,2 t ,[ x } o   fr = } < n k +  o( 1k = } + ) k c ] ak/ [ 】 [ = [ ]bk ; k   / /单位价值  fr = } < I + ) o( 1h n h +  h f rj } n h j +   o( =1 j <= — ; ) + ic 】 c + 】 f 【 < 【 1) (j j   }   c ut o <<e l  nd } p k a sc ( , m t V W , ) = n pak n l i i w, , X }   f r =1j p j +   o( } j <: } ) + f r =li n i +   o( } i <一 }+ ) i ( j = 【) &( 【= ki ) f w【 = t 】 ( 】 i & vj = 【 ) J 】  yi ; 【=1  J c t < ” h  s lc i n i ”  ou < t e ee to s: l {l aj a 】aj 1}【 1 t} t= [;【= 【 】a +1 l 】 j + j =   t=bjI【 = 【+1} [ ] t } 2 [ bj b j 】bj = 2  】 】 +1 t= [ } 】c + 】 D 】 t } 3 c 】 D二 D 1; +1 3 jc c =   f r =1i n i +   o( } i <= }+ ) }   }   it k a sc ( t n f a i t , o t n  n p a k i   , o t l w f a  n l mi l v m x ,



友情链接: