主题:[讨论]求错?
各位大虾们帮帮小弟,我的程序有一处错误找不着,下面的函数就是众所周知的背包问题,我想输出全部的可能结果,可调试结果却不对。
#include <stdio.h>
#define N 6
int main(){
//从N个背包(每个背包中w[k])中选取总重为T的背包,共有多少种选法
int w[N]={1,8,3,4,5,2}; //6个背包
int T=10; //总重
int k=0;
int i=0;
int j=1;
struct stacks{ //栈
int s[N];
int top;
} the_stack;
//初始化栈
for(i=0;i<N;i++) the_stack.s[i]=0;
the_stack.top=0;
do{
while(T>0&&k<=N){
if(T>=w[k]){ //符合条件的背包进栈
the_stack.s[the_stack.top++]=k;
T-=w[k];
}
k++; //不符合则考察下一个背包
}
if(T==0){ //找到一种方法,输出
printf("------------Answer%d------------\n",j);
for(i=0;i<the_stack.top;i++){
printf("%d[%d] ",the_stack.s[i],w[the_stack.s[i]]);
}
j++;
printf("\n");
}
k=the_stack.s[--the_stack.top]; //找不到方法,则前一个入栈的背包出栈,继续考察下一个背包
the_stack.s[the_stack.top]=0;
T+=w[k];
k++;
}while(!(the_stack.top==0&&k==N)); //当栈空且k==N时,所有可能的组合都考察完毕,推出循环
}
[fly]要想成功,就的脚踏实地。[/fly]
#include <stdio.h>
#define N 6
int main(){
//从N个背包(每个背包中w[k])中选取总重为T的背包,共有多少种选法
int w[N]={1,8,3,4,5,2}; //6个背包
int T=10; //总重
int k=0;
int i=0;
int j=1;
struct stacks{ //栈
int s[N];
int top;
} the_stack;
//初始化栈
for(i=0;i<N;i++) the_stack.s[i]=0;
the_stack.top=0;
do{
while(T>0&&k<=N){
if(T>=w[k]){ //符合条件的背包进栈
the_stack.s[the_stack.top++]=k;
T-=w[k];
}
k++; //不符合则考察下一个背包
}
if(T==0){ //找到一种方法,输出
printf("------------Answer%d------------\n",j);
for(i=0;i<the_stack.top;i++){
printf("%d[%d] ",the_stack.s[i],w[the_stack.s[i]]);
}
j++;
printf("\n");
}
k=the_stack.s[--the_stack.top]; //找不到方法,则前一个入栈的背包出栈,继续考察下一个背包
the_stack.s[the_stack.top]=0;
T+=w[k];
k++;
}while(!(the_stack.top==0&&k==N)); //当栈空且k==N时,所有可能的组合都考察完毕,推出循环
}
[fly]要想成功,就的脚踏实地。[/fly]