在討論貪心算法時，我們先了解貪心算法與動態規劃之間的區別與聯系，后面我們將發現可以用0、1背包問題和部分背包問題來比較貪心算法和動態規劃的關系。
我們知道，對于一個最優解問題，貪心算法不一定能夠產生一個最優解。因為，如果想要采用貪心算法得到最優解需要滿足兩個條件：貪心選擇性質、最優子結構。
貪心選擇性質：一個全局最優解可以通過局部最優解來得到。that is to say,當考慮如何做選擇時，我們只考慮對當前問題最佳的選擇而不考慮子問題的結果。
最優子結構：全局最優解包含子問題的最優解。
貪心算法和動態規劃的區別：在動態規劃中，每一步都要做出選擇，但是這些選擇都依賴于子問題的解。因此，解動態規劃問題一般是自底向上，由子問題到問題。在貪心算法中，我們總是做出當前的最好選擇，而這些選擇都不是依賴子問題，選擇后再解決選擇之后出現的子問題。因此，解貪心算法問題一般是自頂向下，一個一個地做出貪心選擇。
從上面的描述可知，動態規劃中解決問題，需要先解決子問題，因此可能用到遞歸（當然可以將遞歸化為非遞歸），計算復雜度要比貪心算法高。從上面的理論解釋可能比較抽象，我們可以用具體的實例來說明問題。我們用經典的0、1背包問題和部分背包問題來看看動態規劃和貪心算法的區別。兩個問題的描述如下：
用貪心選擇算法來解決部分背包問題正如上面所說的思想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背包問題中，我們在選擇是否要加入一個物品時，必須將把該物品加進去的子問題和不加進去的子問題進行比較（選擇依賴子問題），這種方式的問題導致了許多重疊子問題，這是動態規劃的一個特點。
下面我們用動態規劃來解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
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(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
注：如果程序出錯，可能是使用的開發平臺版本不同，請點擊如下鏈接：解釋說明
原文：
