題目描述：有一個(gè)背包，能盛放的物品總重量為S，設(shè)有N件物品，其重量分別為w1,w2,...,wn.希望從N件物品中選擇若干件物品，所選物品的重量之和恰能放入該背包，即所選物品的重量之和等于S。
要求：用非遞歸的方法。
便于理解，先說(shuō)說(shuō)遞歸算法。
非常簡(jiǎn)單：
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：模擬堆棧
也很簡(jiǎn)單，先定義一個(gè)struct Node
typedef struct{
int s;
int n;
int job; //1表示要，2表示不要
}Node;
然后將遞歸的方法用數(shù)組模擬出來(lái)，其實(shí)就是用數(shù)組實(shí)現(xiàn)進(jìn)棧出棧。
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--]; //選取這個(gè)物品
x.job=1;
stack[++top]=x; //進(jìn)棧
}
}
if(!k){ //總重量超出，需要丟棄其中的某個(gè)物品
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;
}
這個(gè)程序算法不復(fù)雜，但是由于平時(shí)這種方法用得少，尤其是stack[top--] stack[++top]這種形式的東東容易搞錯(cuò)，所以考試的時(shí)候我只寫了算法描述。
方法二： 注意到題目并沒(méi)有限制算法的時(shí)間空間，我們用最暴力來(lái)解決：窮舉法
#include <iostream>
using namespace std;
void main()
{
int i,j;
int n,s;//n為物品件數(shù),s為背包容量
cin>>n;
//n = 10;
int *w = new int[n+1];//存儲(chǔ)物品大小
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++)//把物品選中的整個(gè)串當(dāng)作一個(gè)二進(jìn)數(shù)，進(jìn)行范圍的全搜索
{
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) //無(wú)解處理
{
cout<<"no answer"<<endl;
break;
}
}
}