0-1背包问题
问题描述
给定n种物品和一背包，物品i的重量是wi，其价值是pi，背包的容量是M，如何选择装入背包中的物品总价值最大？ 问题分析
记c[i][m] 表示前i个物品，在背包容量大小为m的情况下，最大的装载量。 如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为m的背包中”，价值为c[i-1][m]；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为m-w[i]的背包中”，此时能获得的最大价值就是c[i-1][m-w[i]]再加上通过放入第i件物品获得的价值p[i]。因为背包最大容量M未知。所以，我们的程序要从1到M一个一个的试。比如，开始任选N件物品的一个。看对应M的背包，能不能放进去，如果能放进去，并且还有多的空间，则多出来的空间里能放N-1物品中的最大价值。从以上最大价值的构造过程中可以看出： c(n,m)=max{c(n-1,m), c(n-1,m-w[n])+p(n) 其中c[i-1][m] 表示第i件物品不装入背包中，而c[i-1][m-w[i]] + p[i] 表示第i件物品装入背包中。 伪代码：
1.最优值max(x1*p1+x2*p2+„„xn*pn) int knapsack(int m,int n,int *w,int *p) {
bool a;
for(int i=1;i
for(int j=1;j
{
if(w[i]
{
a=p[i]+c[i-1][j-w[i]]>c[i-1][j];
c[i][j]=a?p[i]+c[i-1][j-w[i]]:c[i-1][j];
//前者表示放i物品，后者表示不放i物品
}
else //i号物品重量大于剩余容量，不能再放i号物品
c[i][j]=c[i-1][j];
}
return(c[n][m]);//最后的值即为最优值，返回主函数 }
2.求最优n元0-1向量(x1,x2,x3„„,xn) int getbest(int m,int n,int *w,int *p) {
if(n==0)return 0;//递归，每次递归n减1，n为0时退出
if(w[n]>m)
{
x[n]=0;
getbest(m,n-1,w,p);
}
else
{
//如果c[n][m]由p[n]+c[n-1][m-w[n]]而来,则x[n]=1;
//如果c[n][m]由c[n-1][m]]而来,则x[n]=0;
x[n]=c[n-1][m]
if(x[n])
getbest(m-w[n],n-1,w,p);
else
getbest(m,n-1,w,p);
} }
程序：
#include #include int c[15][25];//全局变量，初始值全为0 bool x[25];//x数组存n元0-1向量 int knapsack(int m,int n,int *w,int *p) {
bool a;
for(int i=1;i
for(int j=1;j
{
if(w[i]
{
a=p[i]+c[i-1][j-w[i]]>c[i-1][j];
c[i][j]=a?p[i]+c[i-1][j-w[i]]:c[i-1][j];
//前者表示放i物品，后者表示不放i物品
}
else //i号物品重量大于剩余容量，不能再放i号物品
c[i][j]=c[i-1][j];
}
return(c[n][m]);//最后的值即为最优值，返回主函数 }
//求最优n元0-1向量(x1,x2,x3……,xn) int getbest(int m,int n,int *w,int *p) {
if(n==0)return 0;//递归，每次递归n减1，n为0时退出
if(w[n]>m)
{
x[n]=0;
getbest(m,n-1,w,p);
}
else
{
//如果c[n][m]由p[n]+c[n-1][m-w[n]]而来,则x[n]=1;
//如果c[n][m]由c[n-1][m]]而来,则x[n]=0;
x[n]=c[n-1][m]
if(x[n])
getbest(m-w[n],n-1,w,p);
else
getbest(m,n-1,w,p);
} }
void main() {
int m,n; int *w=NULL;
int *p=NULL;
printf(\"输入背包容量和货物个数：\");
scanf(\"%d%d\",&m,&n); p=(int *)calloc(n,sizeof(int));//分配n*sizeof(int)的内存大小，存取n个物品的价格
w=(int *)calloc(n,sizeof(int));//分配n*sizeof(int)的内存大小，存取n个物品的质量
if(!p||!w)//检测分配是否成功
{
printf(\"Not Enough Memory!\\n\");
exit(1);//分配失败，退出
}
for(int i=1;i
printf(\"物品x%d的重量和价值：\",i);
scanf(\"%d%d\",w+i,p+i); }
printf(\"\\n总价值最大为：%d\",knapsack(m,n,w,p));
printf(\"\\n\");
for(i=0;i
for(int j=0;j
{
printf(\"%3d \",c[i][j]);
if(j==m)
printf(\"\\n\");
}
getbest(m,n,w,p);
printf(\"最优n元0-1向量为：\\n\");
for(i=1;i
printf(\"x%d \",i);
printf(\"\\n\");
//打印最优n元0-1向量(x1,x2,x3……,xn)
for(i=1;i
printf(\"%-4d\",x[i]);
printf(\"\\n\"); } 运行结果：
