0 1背包问题数据结构 背包问题

数据结构 背包问题

#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]; ??????????????? ; ??????? } the_stack; ???????//初始化栈 ?????? ?for(i=0;i<N;i++) the_stack.s[i]=0; ??????? the_=0; ??????? do{ ??????????????? while(T>0&&k<=N){ ??????????????????????? if(T>=w[k]){??????????????????????????????????????????????????? //符合条件的背包进栈 ??????????????????????????????? the_stack.s[the_++]=k; ??????????????????????????????? T-=w[k]; ??????????????????????? } ??????????????????????? k++;????????????????????????????????????????????????????????????????? //不符合则考察下一个背包 ??????????????? } ??????????????? if(T==0){??????????????????????????????????????????????????????????????? //找到一种方法，输出 ??????????????????????? printf("------------Answer%d------------ ",j); ??????????????????????? for(i=0;i<the_;i++){ ??????????????????????????????? printf("%d[%d] ",the_stack.s[i],w[the_stack.s[i]]); ??????????????????????? } ??????????????????????? j++; ??????????????????????? printf(" "); ??????????????? } ??????????????? k=the_stack.s[--the_];??????????? //找不到方法，则前一个入栈的背包出栈，继续考察下一个背包 ??????????????? the_stack.s[the_]=0; ??????????????? T+=w[k]; ??????????????? k++; ??????? }while(!(the_==0&&k==N));?????????? //当栈空且k==N时，所有可能的组合都考察完毕，推出循环 } 运行结果： ------------Answer1------------ 0[1] 2[3] 3[4] 5[2] ------------Answer2------------ 0[1] 3[4] 4[5] ------------Answer3------------ 1[8] 5[2] ------------Answer4------------ 2[3] 4[5] 5[2]