Blog·Tanky WooABOUTRSS

《算法导论》学习总结 — 21.第16章 贪心算法(1) 基础入门1

08 Jun 2011
这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。

建议先看看前言: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背包的程序去验证这个结果。

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

#include 
#include 
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> 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 标签: Tanky Woo贪心算法算法导论