题目描述：有一个背包，能盛放的物品总重量为S，设有N件物品，其重量分别为w1,w2,...,wn.希望从N件物品中选择若干件物品，所选物品的重量之和恰能放入该背包，即所选物品的重量之和等于S。
要求：用非递归的方法。
便于理解，先说说递归算法。
非常简单：
int process(int s,int n)
{
if(s==0)return 1;
if(s<0||(s>0&&n<1))return 0;
if(process(s-w[n],n-1))
{
cout<<w[n];
return 1;
}
return process(s,n-1);
} 方法1：模拟堆栈
也很简单，先定义一个struct Node
typedef struct{
int s;
int n;
int job; //1表示要，2表示不要
}Node;
然后将递归的方法用数组模拟出来，其实就是用数组实现进栈出栈。
int Process(int s,int n)
{
STACK stack[100],x;
int top,k,rep;
x.s=s;
x.n=n;
x.job=0;
top=1;
stack[top]=x;
k=0;
while(k==0&&top>0){
x=stack[top];
rep=1;
while(!k&&rep){
if(x.s==0)k=1;
else if(x.s<0||x.n<=0)rep=0;
else {
x.s=x.s-w[x.n--]; //选取这个物品
x.job=1;
stack[++top]=x; //进栈
}
}
if(!k){ //总重量超出，需要丢弃其中的某个物品
rep=1;
while(top>=1&&rep){
x=stack[top--];
if(x.job==1){
x.s+=w[x.n+1]; //丢弃物品
x.job=2;
stack[++top]=x; //出栈
rep=0;
}
}
}
}
if(k){
while(top>=1){
x=stack[top--];
if(x.job==1)cout<<w[x.n+1];
}
}
return k;
}
这个程序算法不复杂，但是由于平时这种方法用得少，尤其是stack[top--] stack[++top]这种形式的东东容易搞错，所以考试的时候我只写了算法描述。
方法二： 注意到题目并没有限制算法的时间空间，我们用最暴力来解决：穷举法
#include <iostream>
using namespace std;
void main()
{
int i,j;
int n,s;//n为物品件数,s为背包容量
cin>>n;
//n = 10;
int *w = new int[n+1];//存储物品大小
int *y = new int[n+1];//物品是否被选中
for(i=1;i<=n;i++)
{
cin>>w[i];//输入物品大小
y[i]=0;
}
cin>>s;
//s = 21;
int t=0;
int flag=0;
while(1)
{
for(i=1;i<=n;i++)//把物品选中的整个串当作一个二进数，进行范围的全搜索
{
if(y[i]==0)
{
y[i]=1;
//cout<<"step in y[i]=0";
break;
}
else
{
if (i==n)
{
flag = 1;
}
y[i]=0;
continue;
}
}
t = 0;
for(j=1;j<=n;j++)
{
t = t+w[j]*y[j];
}
if(t == s)//判断是否求得解，求到解就直接退出
{
for(i=1;i<=n;i++)
{
if(y[i]==1) cout<<w[i]<<" ";
}
break;
}
if(flag == 1) //无解处理
{
cout<<"no answer"<<endl;
break;
}
}
}