参考书目：《算法的乐趣》作者: 王晓华
贪婪法，又叫贪心算法，是寻找最优解问题的常用方法。
基本设计思想的三个步骤：
1）建立对问题的数学建模
2）将问题分解成子问题，同时定义子问题的最优解结构
3）利用贪心原则确定子问题的局部最优解，根据最优解模型，将子问题的局部最优解堆叠出全局最优解
优点：简单高效，省去了为找最优解可能需要的穷举操作，可得到与最优解接近的近似最优解，常作为其他算法的辅助算法使用。
缺点：由于不进行回溯操作，大多数情况下，会错过最优解或者说得不到真正的最优解。
以0-1背包问题作为贪婪法的例子。
0-1背包问题：有N件物品和一件承重为C的背包（或体积），每件物品的重量为Wi，价值为Pi，求解将哪几件物品装入背包可使这些物品在重量总和不超过C的情况下价值总和最大。
背包问题（knapsack problem）是此类组合优化的NP完全问题的总称。类似的比如：货箱装载问题、货船载物问题等。
常见的贪婪策略有三种：
1、根据物品价值选择；
2、根据物品重量选择；
3、定义一个价值密度（Pi/Wi）的概念
下面的代码只涉及第一第二种，在codebook下编译的时候一直有错，找了半天没发现；后来放在VS2015下编译，能够正确编译并且得到正确的答案。很疑惑，代码应该还是有点小问题的也不够严谨。
先把代码存下来，如果有人发现了问题希望能告诉我，谢谢各位！也欢迎提出不足之处！
/*
2018-3-17
贪心算法实现0-1背包问题
copyright @GCN
*/
#include <stdio.h>
#include <stdlib.h>
//策略一：根据物体的价值进行选择
int Pick_P(int p[], int s[], int n)
{
int i, temp = 0, max = 0;
for (i = 0; i<n; i++)
{
if (s[i] == 0 && p[i] >= max)
{
max = p[i];
temp = i;
}
//printf("\n%d,max=%d\n",i,max);
}
return temp;
}
//策略二：根据物体的重量进行选择
int Pick_W(int p[], int s[], int n)
{
int i, temp = 0, min = 99999;
for (i = 0; i<n; i++)
{
if (s[i] == 0 && p[i] <= min)
{
min = p[i];
temp = i;
}
//printf("\n%d,min=%d\n",i,min);
}
return temp;
}
int main()
{
int i, m, xz = 0;
int j = 0, n = 7, ntc = 0, ntp = 0;
int c = 150;//背包容量
int w[] = { 35,30,60,50,40,10,25 };//物体重量
int p[] = { 10,40,30,50,35,40,30 };//物体价值
int s[] = { 0,0,0,0,0,0,0 };//状态
int t[] = { 0 }, tnum = 0;
printf("背包的最大容量:150\n");
printf("物品的个数:7\n");
printf("物体的重量分别为:\n");
for (i = 0; i<n; i++)
{
printf("%d\t", w[i]);
}
printf("\n");
printf("物体的价值分别为:\n");
for (i = 0; i<n; i++)
{
printf("%d\t", p[i]);
}
printf("\n");
printf("物体的初始状态分别为:\n");
for (i = 0; i<n; i++)
{
printf("s[%d]=%d\t", i, s[i]);
}
printf("\n");
printf("以何种策略进行选择(0/1)：");
scanf_s("%d", &xz);
for (m = 0; m<n&&ntc <= c; m++)
{
switch (xz)
{
case 0:
j = Pick_P(p, s, n);
break;
case 1:
j = Pick_W(w, s, n);
break;
}
if ((ntc + w[j]) <= c)
{
ntc += w[j];
ntp += p[j];
s[j] = 1;
t[m] = ntc;
}
else if ((ntc + w[j])>c)
{
s[j] = 2;
}
if ((m != 0 && t[m]>t[m - 1]) || (m == 0 && t[m] <= c))
{
tnum += 1;
printf("\n第%d次:选中第%d件物品,重%d,价值为%d\n", (m + 1), (j + 1), w[j], p[j]);
printf("此时背包中承载的物品重量%d\n", t[m]);
}
else
break;
}
printf("\n共选择%d个物品，总价值为%d\n", tnum, ntp);
return 0;
}
附上实验结果
1、根据物品价值选择；
2、根据物品重量选择；
