神马品牌网百年灵陀飞轮手表:求助：“新”背包问题
来源：百度文库 编辑：神马品牌网 时间：2024/05/07 18:18:52
假设有一个能装入总体积为T的背包和n件体积分别为w1 , w2 , … , wn 的物品，能否从n件物品中挑选若干件恰好装满背包，即使w1 +w2 + … + wn=T，要求找出所有满足上述条件的解。例如：当T=10，各件物品的体积{1，8，4，3，5，2}时，可找到下列4组解：（1，4，3，2）
（1，4，5）
（8，2）
（3，5，2）。
提示：可利用回溯法的设计思想来解决背包问题。首先将物品排成一列，然后顺序选取物品装入背包，假设已选取了前i 件物品之后背包还没有装满，则继续选取第i+1件物品，若该件物品“太大”不能装入，则弃之而继续选取下一件，直至背包装满为止。但如果在剩余的物品中找不到合适的物品以填满背包，则说明“刚刚”装入背包的那件物品“不合适”，应将它取出“弃之一边”，继续再从“它之后”的物品中选取，如此重复，，直至求得满足条件的解，或者无解。
由于回溯求解的规则规则是“后进先出”因此自然要用到栈。
（1，4，5）
（8，2）
（3，5，2）。
提示：可利用回溯法的设计思想来解决背包问题。首先将物品排成一列，然后顺序选取物品装入背包，假设已选取了前i 件物品之后背包还没有装满，则继续选取第i+1件物品，若该件物品“太大”不能装入，则弃之而继续选取下一件，直至背包装满为止。但如果在剩余的物品中找不到合适的物品以填满背包，则说明“刚刚”装入背包的那件物品“不合适”，应将它取出“弃之一边”，继续再从“它之后”的物品中选取，如此重复，，直至求得满足条件的解，或者无解。
由于回溯求解的规则规则是“后进先出”因此自然要用到栈。
我没用堆栈,
要是用的话写的太多了
可能不满足你的要求
#include<iostream.h>
int ta=10;
int p[6];
int n=6;
void putin(int w[],int t,int put,int order=0)
{
int i;
if(t==0)
{
for(i=0;i<put;i++)
cout<<p[i]<<' ';
cout<<endl;
return;
}
if(t<0 || order==n)
return;
for(i=order;i<n;i++)
{
p[put]=w[i];
putin(w,t-w[i],n,put+1,i+1);
}
}
void main()
{
int w[]={1,8,4,3,5,2};
putin(w,ta,6,0);
}