贪心算法总结_贪心算法的解向量

                                       贪心算法总结
1

一、算法思想
贪心法的基本思路：
从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。
该算法存在问题：
1. 不能保证求得的最后解是最佳的；
2. 不能用来求最大或最小解问题；
3. 只能求满足某些约束条件的可行解的范围。
实现该算法的过程：
从问题的某一初始解出发；
while 能朝给定总目标前进一步；
求出可行解的一个解元素；
由所有解元素组合成问题的一个可行解；

二、ACM做题情况
本专题，学习贪心算法，所给的18道题中只AC了14道（其中还有两题相同），除了几道水题以外，大部分题目是用到贪心算法来解决的，做了这套题，虽然感觉很困难，但想办法还是能AC几道题的，做过这些题目使我对贪心算法印象加深，没有以前感觉那么抽象，算是有进步吧，但还是不熟练，还需要加强训练。简短截说，还是在复习回顾一下，关于贪心算法的经典题目吧。

三、典型例题分类分析

【背包问题】

给定一个载重量为M的背包，考虑n个物品，其中第i个物品的重量 ，价值wi （1≤i≤n），要求把物品装满背包，且使背包内的物品价值最大。
有两类背包问题（根据物品是否可以分割），如果物品不可以分割，称为0—1背包问题（动态规划）；如果物品可以分割，则称为背包问题（贪心算法）。

有3种方法来选取物品：
（1）当作0—1背包问题，用动态规划算法，获得最优值220；
（2）当作0—1背包问题，用贪心算法，按性价比从高到底顺序选取物品，获得最优值160。由于物品不可分割，剩下的空间白白浪费。
（3）当作背包问题，用贪心算法，按性价比从高到底的顺序选取物品，获得最优值240。由于物品可以分割，剩下的空间装入物品3的一部分，而获得了更好的性能。

struct bag{
    int w;          //物品的重量
    int v;          //物品的价值
    double c;       //性价比
}a[1001];           //存放物品的数组
1
2
3
4
5

排序因子（按性价比降序）：
bool cmp(bag a, bag b){
    return a.c >= b.c;
}
1
2
3
4

//形参n是物品的数量，c是背包的容量M，数组a是按物品的性价比降序排序
double knapsack(int n, bag a[], double c)
{
　　double cleft = c;　　　　　　　　//背包的剩余容量
　　int i = 0;
　　double b = 0;　　　　　　　　　　//获得的价值
　　//当背包还能完全装入物品i
　　while(i<n && a[i].w<cleft)
　　{
　　　　cleft -= a[i].w;
　　　　b += a[i].v;
　　　　i++;
　　}
　　//装满背包的剩余空间
　　if (i<n) b += 1.0*a[i].v*cleft/a[i].w;
　　return b;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

如果要获得解向量，则需要在数据结构中加入物品编号：
struct bag{
    int w;
    int v;
    double x;       
1
2
3
4
5