建議先看看前言：http://www.wutianqi.com/?p=2298
連載總目錄：http://www.wutianqi.com/?p=2403
說到貪心算法，避免不了于DP對比，所以前面的DP要了解。
貪心算法是使所做的選擇看起來都是當(dāng)前最佳的，期望通過所做的局部最優(yōu)選擇來產(chǎn)生一個(gè)全局最優(yōu)解。
依然和上一章總結(jié)DP一樣，我先給出一個(gè)最容易入門的例子，來看看神馬是貪心？(是人就會(huì)貪心，這個(gè)算法很人性化啊
=。=)
一個(gè)最簡單的例子：
部分背包問題：
有N個(gè)物品，第i個(gè)物品價(jià)值vi，重wi，現(xiàn)在你有一個(gè)可以裝W 磅的包，你可以選擇帶走每個(gè)物品的全部或一部分，求如何選擇可以使背包所裝的價(jià)值最大？(這個(gè)是不是和前面DP中講的01背包很像？認(rèn)真看清楚兩者題目的不同！)
假如有三種物品，背包可裝50磅的物品，物品1重10磅，價(jià)值60元；物品2重20磅，價(jià)值100元；物品3重30磅，價(jià)值120元。因此，既然可以選擇只裝一部分，我們可以算出每種物品的單位價(jià)值，物品1是每磅6元，物品2是美邦5元，物品3是每磅4元。按照貪心策略，應(yīng)該現(xiàn)狀物品1，如果裝完物品1背包還有空間，再裝物品2……
最后的結(jié)果是：
而如果按01背包，則結(jié)果是：
有興趣的可以拿我那01背包的程序去驗(yàn)證這個(gè)結(jié)果。
下面是一個(gè)部分背包的小程序：
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 << "輸入物品個(gè)數(shù): ";
cin >> n;
cout << "輸入背包可載重量: ";
cin >> W;
cout << "輸入" << n << "個(gè)物品的價(jià)值和重量:" << 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 << "最大價(jià)值是: " << value << endl;
return 0;
} |
結(jié)果如圖：
Tanky Woo 標(biāo)簽:
Tanky Woo，
貪心算法，
算法導(dǎo)論
posted on 2011-06-14 13:17
Tanky Woo 閱讀(1797)
評論(5) 編輯 收藏 引用