算法设计与分析W12-近似算法

VIP免费

2025-01-13 0 0 2.69MB 159 页 5.9玖币

侵权投诉

近似算法

Approximation Algorithms

近似算法的设计方法

贪心算法

旅行商问题

背包问题

最小顶点覆盖问题

局部搜索

( local search)

线性规划

随机算法

动态规划

u… …

最大背包问题

（

Maximum Knapsack

）

背包问题

输入：

个物品的集合

U={u1, u2, ..., un}

，其中物品

的重量记为

w(ui)

，价值记为

v(ui)

，

i =1, 2,..., n

；

一个承重为

的背包，

输出：价值最高的物品子集

!:"U

，且能全部放入

背包中，即

max{#;∈=#$ % &!:"!'#;∈=#( % )*}

背包问题的近似算法

——

贪心算法

贪心策略

把物品按照重量

进行降序排序

把物品按照价值

进行降序排序

把物品按照价值重量比

vi /wi

进行降序排序

背包问题的近似算法

——

贪心算法

算法

KnapsackGreedy

输入：

个物品

ui,

重量

w(ui),

价值

v(ui), i=1,2,..., n

，

承重

输出：最大价值物品子集

U '

，满足总重量

≤ W

对给定的物品计算价值重量比

vi /wi, i=1,2,..., n

把物品按价值重量比的降序排列，形成有序列表

重复以下步骤，直至有序列表中不留下物品

当前物品能够放入背包，则加入

U′

；

否则，考虑下一物品；

输出

U′

例：

背包的承重量

等于

。

物品重量价值

1 3 12

2 4 40

3 5 25

4 7 42

价值重量比

例：

背包的承重量

等于

。

算法选择物品顺序为：

物品

（超过承重）

物品

（超过承重）

物品重量价值

1 3 12

2 4 40

3 5 25

4 7 42

价值重量比

得，

Uʹ={

物品

，物品

。

价值和为

总重量为

9<10

近似性能比？

例

算法输出为

{

物品

，总价值为

最优解为

{

物品

，总价值为

解的精度为

W/2

，没有上界

算法的性能比为

∞

物品重量价值

1 1 2

2W W

价值重量比

是否具有常数性

能比算法？

背包的承重量

W>2

增强贪心算法

（

Enhanced greedy algorithm

）

物品重量价值

1 1 2

2W W

价值重量比

198

算法

KnapsackGreedy-Enhanced

输入：

个物品

ui,

重量

w(ui),

价值

v(ui), i =1,2,..., n

，承重

量

输出：最大价值物品子集，满足总重量

≤ W

1. U′ = KnapsackGreedy(U, w, v, W)

令

umax

是能放入箱子的物品中具有最大价值的物品

输出

U′

与

umax

中价值最大者

max{v(U′), v(umax)}

背包的承重量

W>2

算法输出｛物品

｝

定理

：对于背包问题，增强贪心算法是一个

近似算法。

假设最优解为

，则一定有

m*(x)<Vj + vj

。

（考虑分数背包问题，此时

Vj+vj

一

定大于分数背包问

题的最优值，而分数背包问题最优值一定大于或等于

0-1

背包问题的最优值。）

证明：

给定背包问题的实例

，记

按价值重量比降序排列后物体序列为

u1,…,un,

对应的价值序列为

: v1,…,vn,

重量序列为

w1,…,wn

。

假设

是第一个不能放入箱子中的物品，此时箱子中物

品为

u1,…, uj-1,

未放入箱子中的物品为

uj ,…, un

。

则箱子中物品的总价值为

+,>-#9-.

>$. $9,

总重为

*>-#9-.

>$. (9)*.

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

5.9 玖币 0人已下载

立即下载 VIP免费下载

摘要：

近似算法ApproximationAlgorithms近似算法的设计方法u贪心算法ü旅行商问题ü背包问题ü最小顶点覆盖问题u局部搜索(localsearch)u线性规划u随机算法u动态规划u……91最大背包问题（MaximumKnapsack）背包问题ü输入：n个物品的集合U={u1,u2,...,un}，其中物品ui的重量记为w(ui)，价值记为v(ui)，i=1,2,...,n；一个承重为W的背包，ü输出：价值最高的物品子集=:⊆U，且能全部放入背包中，即max{∑;∈=#>?|=:⊆=,∑;∈=#A?≤B}92背包问题的近似算法——贪心算法u贪心策略ü把物品按照重量wi进行降序排序ü把物...

展开>> 收起<<

算法设计与分析W12-近似算法.pdf

共159页,预览32页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

算法设计与分析W12-近似算法

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: