使用贪心策略求解此类问题时，首先要选出最优的度量标准。
可供选择的度量标准有三种：价值，容量，单位价值（v/w，价值/重量）。
显然，价值高的物品容量可能太大，容量大的物品价值也可能很低。最优的度量标准是单位价值。
背包问题算法思路：
1、将各个物品按照单位价值由高到低排序；
2、取价值最高者放入背包；
3、计算背包的剩余空间；
4、重复2-3步，直到背包剩余容量=0或者物品全部装入背包为止（对于0-1背包，终止条件为背包剩余容量无法装入任意一件物品或者物品全部装入背包）。
#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=0i<ni++)
{
x[i] = 0//初始状态，所有物品都没有被放入背包
}
for(i=0i<ni++)
{
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=0i<ni++)
{
x[i] = 0//初始状态，所有物品都没有被放入背包
}
for(i=0i<ni++)
{
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=0i<ni++)
{
x[i] = 0//初始状态，所有物品都没有被放入背包
}
for(i=0i<ni++)
{
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=0i<ni++)
{
x[i] = 0//初始状态，所有物品都没有被放入背包
}
for(i=0i<ni++)
{
if(w[i] >c)
{
break
}
x[i] = 1
c = c - w[i]
printf("放入第%d件物品，背包剩余容量%f.\n",(i+1),c)
}
}
01背包问题就是有个容量为W的包，然后有一堆的物品(1...n)，其中wi、vi分别为第i个物品的重量和价值，现在需要求的就是使得包中所装的物品尽可能的价值高。那么这个物品放不放在包中对应取值0or
1。其算法为动态规划，需要证明最优子结构性质。用s[i][j]表示只有前i个物品且包容量为j时所能等到的最大价值，而有递归式
s[i][j]=
s[i-1][j],
wi>j
max{s[i-1][j],s[i-1][j-wi]+vi},
wi<=j
s[0][j]=0
1<=j<=W
s[i][0]=0
1<=i<=n
所以不论用什么语言实现，就是计算上面的式子，最终求得s[n][W]，上面的式子很好用递推实现的，这个是自底向上的，就是两层for；你也可以用栈实现自顶向下的，这个是记录式的方法。
以上的W是只考虑整数的。
提问者的这程序中用了递归算法，不过逻辑上有个小bug，就是在判断到n==0时，如果还有容量，那么返回的应该是第一个物品的重量而不是0。你可以改变容量C或物品参数来检验算法的逻辑正确性。
关于输出选择的物品，我加了一个数组，用来标记选择的物品。因为做完所有递归后只有最外层的标记是有效的，所以最后用了一个for循环来完成各层的标记。下面是改动后的程序：
int a[5]={0}int MaxW(int n, int C, int *Volunme, int *Weight)
{
int W=0,W1=0,W2=0
if (n == 0)
{
if(C >= Volunme[0])
{
a[0]=1
return W=1
}
else
return 0
}
else if(C >= Volunme[n])//背包剩余空间可以放下物品n
{
W1 = MaxW(n-1, C-Volunme[n],Volunme,Weight) + Weight[n] //放入n所能得到的重量
W2 = MaxW(n-1,C,Volunme,Weight) //不放n所能得到的重量
W=(W1>W2?W1:W2)
a[n]=(W1>W2?1:0)
}
else//背包空间放不下n,返回判断放n-1的情况
{
return MaxW(n-1,C,Volunme,Weight)
}
return W
}
int main(void)
{
int n=5int C=7
int Volunme[] = {1,2,3,4,5}
int Weight[] = {1,2,5,7,8}
printf("最大重量为%d\n",MaxW(n-1,C,Volunme,Weight))
for(int i=n-2i>=0i--)
{
a[i]=0
if(a[i+1]==1)
{
C-=Volunme[i+1]
Weight[i+1]=0
}
MaxW(i,C,Volunme,Weight)
}
printf("选择的物品号是：")
for(int i=0i<5i++)
{
if(a[i]==1)
printf("#%d ",i+1)
}
printf("\n")
return 0
}
