問題描述:
給定n種物品和一個背包。物品i的重量為w[i]，其價值為v[i]，背包的容量為c。應如何選擇裝入 背包的物品，使得裝入背包中的物品的總價值最大。每種物品最多裝入一次。
0-1背包問題：對於要裝入背包中的物品，只有兩種選擇：全部裝入或者不裝入。
背包問題：對於要裝入背包中的物品，可以選擇裝入一部分，不一定要全部裝入背包中。
算法分析：
使用貪心策略求解此類問題時，首先要選出最優的度量標准。
可供選擇的度量標准有三種：價值，容量，單位價值（v/w，價值/重量）。
顯然，價值高的物品容量可能太大，容量大的物品價值也可能很低。最優的度量標准是單位價值。
背包問題算法思路：
1、將各個物品按照單位價值由高到低排序；
2、取價值最高者放入背包；
3、計算背包的剩余空間；
4、重復2-3步，直到背包剩余容量=0或者物品全部裝入背包為止（對於0-1背包，終止條件為背包剩余容量無法裝入任意一件物品或者物品全部裝入背包）。
下面是C語言實現（DEV c++4.9.9.2運行通過）
[cpp]
#include<stdio.h>
void package(int n,float c,float v[],float w[],float x[]);
void package0_1(int n,float c,float v[],float w[],float x[]);
int main(void)
{
int n = 3;
float c = 20;
float v[] = {24,15,25};
float w[] = {15,10,18};//已經按照單位價值降序排列
float *x;
x = (float*)malloc(sizeof(float)*n);
printf("******背包*******\n");
package(n,c,v,w,x);
printf("*******0-1背包******\n");
package0_1(n,c,v,w,x);
system("PAUSE");
}
/*
* 背包問題
* n:物品個數
* c：背包容量
* v[]:每個物品的價值
* w[]:每個物品的重量（這裡已經按照單位價值降序排列 ）
* x[]:物品是否放入背包（0表示不放，1表示全部放入，0-1放入一部分）
*/
void package(int n,float c,float v[],float w[],float x[])
{
int i;
for(i=0;i<n;i++)
{
x[i] = 0;//初始狀態，所有物品都沒有被放入背包
}
for(i=0;i<n;i++)
{
if(w[i] > c)
{
break;
}
x[i] = 1;
c = c - w[i];
printf("放入第%d件物品，背包剩余容量%f.\n",(i+1),c);
}
if(i<=n)//還可以放入一個物品的一部分
{
x[i] = c/w[i];
printf("放入第%d件物品的%f部分.背包剩余容量為0.\n",(i+1),w[i]*x[i]);
}
}
/*
* 0-1背包問題
* n:物品個數
* c：背包容量
* v[]:每個物品的價值
* w[]:每個物品的重量（這裡已經按照單位價值降序排列 ）
* x[]:物品是否放入背包（0表示不放，1表示全部放入）
*/
void package0_1(int n,float c,float v[],float w[],float x[])
{
int i;
for(i=0;i<n;i++)
{
x[i] = 0;//初始狀態，所有物品都沒有被放入背包
}
for(i=0;i<n;i++)
{
if(w[i] > c)
{
break;
}
x[i] = 1;
c = c - w[i];
printf("放入第%d件物品，背包剩余容量%f.\n",(i+1),c);
}
}
#include<stdio.h>
void package(int n,float c,float v[],float w[],float x[]);
void package0_1(int n,float c,float v[],float w[],float x[]);
int main(void)
{
int n = 3;
float c = 20;
float v[] = {24,15,25};
float w[] = {15,10,18};//已經按照單位價值降序排列
float *x;
x = (float*)malloc(sizeof(float)*n);
printf("******背包*******\n");
package(n,c,v,w,x);
printf("*******0-1背包******\n");
package0_1(n,c,v,w,x);
system("PAUSE");
}
/*
* 背包問題
* n:物品個數
* c：背包容量
* v[]:每個物品的價值
* w[]:每個物品的重量（這裡已經按照單位價值降序排列 ）
* x[]:物品是否放入背包（0表示不放，1表示全部放入，0-1放入一部分）
*/
void package(int n,float c,float v[],float w[],float x[])
{
int i;
for(i=0;i<n;i++)
{
x[i] = 0;//初始狀態，所有物品都沒有被放入背包
}
for(i=0;i<n;i++)
{
if(w[i] > c)
{
break;
}
x[i] = 1;
c = c - w[i];
printf("放入第%d件物品，背包剩余容量%f.\n",(i+1),c);
}
if(i<=n)//還可以放入一個物品的一部分
{
x[i] = c/w[i];
printf("放入第%d件物品的%f部分.背包剩余容量為0.\n",(i+1),w[i]*x[i]);
}
}
/*
* 0-1背包問題
* n:物品個數
* c：背包容量
* v[]:每個物品的價值
* w[]:每個物品的重量（這裡已經按照單位價值降序排列 ）
* x[]:物品是否放入背包（0表示不放，1表示全部放入）
*/
void package0_1(int n,float c,float v[],float w[],float x[])
{
int i;
for(i=0;i<n;i++)
{
x[i] = 0;//初始狀態，所有物品都沒有被放入背包
}
for(i=0;i<n;i++)
{
if(w[i] > c)
{
break;
}
x[i] = 1;
c = c - w[i];
printf("放入第%d件物品，背包剩余容量%f.\n",(i+1),c);
}
}
雖然背包問題和0-1背包都具有最優子結構性質，但是背包問題用貪心算法求出來的是最優解，0-1背包問題通過貪心算法得不到最優解，因為無法保證最後能將背包裝滿，部分閒置的背包空間使總價值降低了。
