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

連載總目錄：http://www.wutianqi.com/?p=2403

說到貪心算法，避免不了于DP對(duì)比，所以前面的DP要了解。

貪心算法是使所做的選擇看起來都是當(dāng)前最佳的，期望通過所做的局部最優(yōu)選擇來產(chǎn)生一個(gè)全局最優(yōu)解。

依然和上一章總結(jié)DP一樣，我先給出一個(gè)最容易入門的例子，來看看神馬是貪心？(是人就會(huì)貪心，這個(gè)算法很人性化啊

=。=)

一個(gè)最簡(jiǎn)單的例子：

部分背包問題：

有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; // valuedouble 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)論

在我獨(dú)立博客上的原文：http://www.wutianqi.com/?p=2571

歡迎各位探討。

轉(zhuǎn)載于:https://www.cnblogs.com/tanky_woo/archive/2011/06/14/2080522.html

總結(jié)

以上是生活随笔為你收集整理的《算法导论》学习总结 — 21.第16章 贪心算法(1) 基础入门1的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。