在讨论贪心算法时，我们先了解贪心算法与动态规划之间的区别与联系，后面我们将发现可以用0、1背包问题和部分背包问题来比较贪心算法和动态规划的关系。
我们知道，对于一个最优解问题，贪心算法不一定能够产生一个最优解。因为，如果想要采用贪心算法得到最优解需要满足两个条件：贪心选择性质、最优子结构。
贪心选择性质：一个全局最优解可以通过局部最优解来得到。that is to say,当考虑如何做选择时，我们只考虑对当前问题最佳的选择而不考虑子问题的结果。
最优子结构：全局最优解包含子问题的最优解。
贪心算法和动态规划的区别：在动态规划中，每一步都要做出选择，但是这些选择都依赖于子问题的解。因此，解动态规划问题一般是自底向上，由子问题到问题。在贪心算法中，我们总是做出当前的最好选择，而这些选择都不是依赖子问题，选择后再解决选择之后出现的子问题。因此，解贪心算法问题一般是自顶向下，一个一个地做出贪心选择。
从上面的描述可知，动态规划中解决问题，需要先解决子问题，因此可能用到递归（当然可以将递归化为非递归），计算复杂度要比贪心算法高。从上面的理论解释可能比较抽象，我们可以用具体的实例来说明问题。我们用经典的0、1背包问题和部分背包问题来看看动态规划和贪心算法的区别。两个问题的描述如下：
用贪心选择算法来解决部分背包问题正如上面所说的思想，十分简单，在这里就不给予程序实现。我们主要讨论0、1背包问题的最优解。
下面我们例子来说明为什么贪心选择算法不能解0、1背包问题：假设背包容量为116，序号为1-3的物品的重量和价格分别为：w[3]={100，14，10},p[3]={20，18，15}.其平均价值为｛0.2，18/14，1.5｝，按照贪心算法的话，选择物品顺序为：3，2，1，最终的选择为3，2，其价值为33，但是实际的最优方案为：选择1，2，其价值为38.
从这个例子中可以看出，在0、1背包问题中，我们在选择是否要加入一个物品时，必须将把该物品加进去的子问题和不加进去的子问题进行比较（选择依赖子问题），这种方式的问题导致了许多重叠子问题，这是动态规划的一个特点。
下面我们用动态规划来解0、1背包问题：假设f[i][j]表示剩余物品为i,i+1,……n,容量为j时的最大价值，例如以上面的例子来说明，f[0][10]，表示物品为1，2，3，容量为116时的最大价值，f[1][116]，表示物品为2，3，容量为116时的最大价值。我们目的是求f[0][116],利用动态规划的思想，假设我们选择1号物品，则最大价值为p[0]+f[1][116-100],如果不选1号，则最大价值为f[1][116],因此选不选1号则需要比较两者的最大值。比较两者的最大值需要求f[1][116]和f[1][116-100]，这是重叠子问题。最终的表达式为：f[i][j]=f[i+1][j]>f[i+1][j-w[i]]+p[i].这个表达式可以递归求解，当然也可以迭代求解。
具体程序实现如下：
#include<stdio.h>
int Bag_0or1(int *w,int *p,int *flag,int n,int i,int y);
void Bag_0or1_iteration(int *w,int *p,int c,int n,int f[][116]);
void print(int *w,int *flag,int n,int c,int f[][116]);
void main()
{
int w[]={100,14,10};//被注释的部分是另外一个实例
int p[]={20,18,15};
int c=116;
int n=2;
//int w[]={2,2,6,5,4};
//int p[]={6,3,5,4,6};
//int c=10;
//int n=4;//n为物品个数减一，是因为数组从0开始。
int i=0;
int f[5][116]={0};
int flag[5]={0};//flag为1表示选择该物品
printf("最大价值为：%d\n",Bag_0or1(w,p,flag,n,i,c));
printf("选择的物品为（1表示选择，0表示未选择）：");
printf("%d%d%d\n",flag[0],flag[1],flag[2]);
//Bag_0or1_iteration(w,p,c-1,n,f);
//printf("最大价值为：%d\n",f[0][c-1]);
//printf("选择的物品为（1表示选择，0表示未选择）：");
//print(w,flag,n,c-1,f);
//printf("\n");
}
/***************************************************\
函数功能：递归法解0/1背包问题
输入： 物品重量w、物品价格p,物品个数n、i,y表示剩余容量为y,剩余物品为i,i+1,……n
输出： 背包所能容下的最大价值
\***************************************************/
int Bag_0or1(int *w,int *p,int *flag,int n,int i,int y)//递归法
{
if(i==n)//物品仅剩余最后一件
{
if(y<w[n])
{
flag[n]=0;
return 0;
}
else
{
flag[n]=1;
return p[n];
}
}
if(y<w[i])//当物品i加入后大于容量的情况
{
flag[i]=0;
printf("ok");
return Bag_0or1(w,p,flag,n,i+1,y);
}
if(Bag_0or1(w,p,flag,n,i+1,y)>(Bag_0or1(w,p,flag,n,i+1,y-w[i])+p[i]))
//当物品i加入后还有剩余容量的情况
{
flag[i]=0;
return Bag_0or1(w,p,flag,n,i+1,y);
}
else
{
flag[i]=1;
return Bag_0or1(w,p,flag,n,i+1,y-w[i])+p[i];
}
}
/***************************************************\
函数功能：迭代法解0/1背包问题
输入： 物品重量w、物品价格p,物品个数n、i,y表示剩余容量为y,剩余物品为i,i+1,……n，
f[i][j]表示剩余物品为i,i+1,……n,容量为j时的最大价值
输出： 无
\***************************************************/
void Bag_0or1_iteration(int *w,int *p,int c,int n,int f[][116])//迭代法
{
for(int y=0;y<=c;y++)//初始化
f[n][y]=0;
for(int y=w[n];y<=c;y++)//这里有很多y值根本用不到，但是由于不能知道y的取值，所以要考虑所有y的取值
f[n][y]=p[n];
for(int i=n-1;i>0;i--)
{
for(int y=0;y<=c;y++)
f[i][y]=f[i+1][y];
for(int y=w[i];y<=c;y++)//选择当前物品i是否装入
{
if(f[i+1][y]>(f[i+1][y-w[i]]+p[i]))
f[i][y]=f[i+1][y];//不装入
else
f[i][y]=f[i+1][y-w[i]]+p[i];//装入
}
}
f[0][c]=f[1][c];
if(c>=w[0])//考虑是否将第一个物品装入
{
if(f[0][c]>(f[1][c-w[0]]+p[0]))
f[0][c]=f[0][c];
else
f[0][c]=f[1][c-w[0]]+p[0];
}
}
/***************************************************\
函数功能：打印被选择的物品
输入： 物品重量w、是否被选择的标志flag,物品个数n、c为背包容量
f[i][j]表示剩余物品为i,i+1,……n,容量为j时的最大价值
输出： 无
\***************************************************/
void print(int *w,int *flag,int n,int c,int f[][116])
{
for(int i=0;i<n;i++)
{
if(f[i][c]==f[i+1][c])//不装入序号为i的物品的情况
flag[i]=0;
else
{
flag[i]=1;
c=c-w[i];
}
flag[n]=(f[n][c])?1:0;
}
for(int j=0;j<=n;j++)
printf("%d",flag[j]);
}
注：如果程序出错，可能是使用的开发平台版本不同，请点击如下链接： 解释说明
原文：http://blog.csdn.net/tengweitw/article/details/17054009
作者：nineheadedbird
