标题:[经验]贪心算法
只看楼主
老衲还俗了
Rank: 1
等 级:新手上路
帖 子:5
专家分:0
注 册:2007-6-4
 问题点数:0 回复次数:2 
[经验]贪心算法


一、算法思想

贪心法的基本思路:
——从问题的某一个初始解出发逐步逼近给定的目标,以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时,算法停止
该算法存在问题:
1. 不能保证求得的最后解是最佳的;
2. 不能用来求最大或最小解问题;
3. 只能求满足某些约束条件的可行解的范围。


实现该算法的过程:
从问题的某一初始解出发;
while 能朝给定总目标前进一步 do
   求出可行解的一个解元素;
由所有解元素组合成问题的一个可行解;

二、例题分析

1、[背包问题]有一个背包,背包容量是M=150。有7个物品,物品可以分割成任意大小。
要求尽可能让装入背包中的物品总价值最大,但不能超过总容量。

物品 A B C D E F G
重量 35 30 60 50 40 10 25
价值 10 40 30 50 35 40 30


分析:

目标函数: ∑pi最大
约束条件是装入的物品总重量不超过背包容量:∑wi<=M( M=150)


(1)根据贪心的策略,每次挑选价值最大的物品装入背包,得到的结果是否最优?
(2)每次挑选所占空间最小的物品装入是否能得到最优解?
(3)每次选取单位容量价值最大的物品,成为解本题的策略。 ?

搜索更多相关主题的帖子: 算法 贪心 经验 目标 
2007-06-04 10:32
nuciewth
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:我爱龙龙
等 级:贵宾
威 望:104
帖 子:9786
专家分:208
注 册:2006-5-23
得分:0 
只能说某一类背包问题是用贪心法解.

倚天照海花无数,流水高山心自知。
2007-06-04 11:33
zkkpkk
Rank: 2
等 级:论坛游民
威 望:5
帖 子:489
专家分:28
注 册:2006-6-17
得分:0 
谈心最后得出的一般是次优较优

Viva,espana!
2007-06-04 21:17



参与讨论请移步原网站贴子:https://bbs.bccn.net/thread-144705-1-1.html




关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.251190 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved