随笔 - 70  文章 - 160  trackbacks - 0

公告:
知识共享许可协议
本博客采用知识共享署名 2.5 中国大陆许可协议进行许可。本博客版权归作者所有,欢迎转载,但未经作者同意不得随机删除文章任何内容,且在文章页面明显位置给出原文连接,否则保留追究法律责任的权利。 具体操作方式可参考此处。如您有任何疑问或者授权方面的协商,请给我留言。

常用链接

留言簿(8)

随笔档案

文章档案

搜索

  •  

积分与排名

  • 积分 - 176282
  • 排名 - 145

最新评论

阅读排行榜

评论排行榜

建议先看看前言:http://www.wutianqi.com/?p=2298

连载总目录:http://www.wutianqi.com/?p=2403

说到贪心算法,避免不了于DP对比,所以前面的DP要了解。

贪心算法是使所做的选择看起来都是当前最佳的,期望通过所做的局部最优选择来产生一个全局最优解。

依然和上一章总结DP一样,我先给出一个最容易入门的例子,来看看神马是贪心?(是人就会贪心,这个算法很人性化啊

=。=)

一个最简单的例子:

部分背包问题:

有N个物品,第i个物品价值vi,重wi,现在你有一个可以装W 磅的包,你可以选择带走每个物品的全部或一部分,求如何选择可以使背包所装的价值最大?(这个是不是和前面DP中讲的01背包很像?认真看清楚两者题目的不同!)

假如有三种物品,背包可装50磅的物品,物品1重10磅,价值60元;物品2重20磅,价值100元;物品3重30磅,价值120元。因此,既然可以选择只装一部分,我们可以算出每种物品的单位价值,物品1是每磅6元,物品2是美邦5元,物品3是每磅4元。按照贪心策略,应该现状物品1,如果装完物品1背包还有空间,再装物品2……

16_2

最后的结果是:

16_3

而如果按01背包,则结果是:

16_4

有兴趣的可以拿我那01背包的程序去验证这个结果。

下面是一个部分背包的小程序:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
 
#include <iostream>
#include <algorithm>
using namespace std;
 
typedef struct Thing{
	double v;     // value
	double w;     // weight
}Thing;
 
Thing arr[100];
int n;
double W;
 
 
bool cmp(Thing a, Thing b)
{
	return a.v/a.w > b.v/b.w;
}
 
 
int main()
{
	cout << "输入物品个数: ";
	cin >> n;
	cout << "输入背包可载重量: ";
	cin >> W;
	cout << "输入" << n << "个物品的价值和重量:" << endl;
	for(int i=0; i<n; ++i)
		cin >> arr[i].v >> arr[i].w;
	sort(arr, arr+n, cmp);
	int k = 0;
	double value = 0;
	while(W)
	{
		if(W >= arr[k].w)
		{
			W -= arr[k].w;
			value += arr[k].v;
		}
		else
		{
			value += W * arr[k].v / arr[k].w;
			W = 0;
		}
		++k;
	}
	cout << "最大价值是: " << value << endl;
	return 0;
}

结果如图:

16_1

Tanky Woo 标签: 
posted on 2011-06-14 13:17 Tanky Woo 阅读(1667) 评论(5)  编辑 收藏 引用

FeedBack:
# re: 《算法导论》学习总结 — 21.第16章 贪心算法(1) 基础入门1 2011-06-14 16:12 吹着风
某种传染病第一天只有一个患者,前五天为潜伏期,不发作也不会传染人 第6天开始发作,从发作到治愈需要5天时间,期间每天传染3个人 求第N天共有多少患者
请教这个题目怎么做?
递归怎么写?  回复  更多评论
  
# re: 《算法导论》学习总结 — 21.第16章 贪心算法(1) 基础入门1 2011-06-15 09:46 lugesot
把处于潜伏期的人按的病天数分配给5个变量,再加一个得病人数和一个治愈人数变量
  回复  更多评论
  
# re: 《算法导论》学习总结 — 21.第16章 贪心算法(1) 基础入门1 2011-06-15 10:48 吹着风
能把实现写出来更好!  回复  更多评论
  
# re: 《算法导论》学习总结 — 21.第16章 贪心算法(1) 基础入门1 2012-11-24 17:16 
信息分析的依据一旦没有了,那么对于现实的动作与行为之间的分解的出来的过程确实是难以量化的一种结果,但是自己要做的事情不过是让这样的一种信息分析暂时失去信息依据的分析下面自己对于事情的分析的效果究竟怎么样的一种,  回复  更多评论
  
# re: 《算法导论》学习总结 — 21.第16章 贪心算法(1) 基础入门1 2013-02-13 19:33 
今天的工作状态实际上是一种巅峰下面的无效状态,或者说迷惑当中的无知状态当中度过整个的7个小时,就本身的7个小时的工作状态来说,实际上建立在顾客需求的态度上面就是一种逼迫顾客想法的状态  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理