解释一下背包问题(C++)

粗略看了一下, 应该是这样的:
int w[MAXSIZE];/*按照从小到大的顺序存放各物品的重量值*/ 但w[0]不放物品重量值
/**
knapsack(int s,int m)中s是背包剩余空间,m是当前要装的物品下标,从最大的开始;比如有5个物品,背包的总空间是30的话第一次调用时是knapsack(30, 5)
*/
int knapsack(int s,int m)
{int s1,b;
if(s==0) return 1;/*成功刚返回1*/ s==0表示背包已装满了所以成功返回
esle if((s<w[1])||m==0) return 0;/*无解*/ s<w[1], w[1]是所有物品中最小的一个,如果背包剩余空间连最小的都装不下肯定就无解了;因为物品下标从1开始, m==0表示物品已试装完了,这时要么回溯要么返回失败0
else{
do{
s1=w[m]; //把第m个物品装入背包
m--; //准备装下一个
b=knapsack(s-s1,m);//装下一个物品,这时的背包剩余空间是s-s1
}while((m!=0)&&(!b)); //如果还有物品, 并且上一次装入成功就继续

if(!b) return 0; //如果上一次安装失败就返回,否则输出成功装入的物品
else {
printf("\n%d",s1);
return 1;
}
}
}
//从上面看出这个算法只求一个解, 没有求最优解. 要把递归好好理解才能看通, 最好做个例子走一遍

你没有给出具体得程序,但这是一个递归问题,就是自上而下得方法去解决,你学习一下递归就可以了

。