Question

数据结构 背包问题

假设有一个能装入总体积为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）。

Answer 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];
                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时，所有可能的组合都考察完毕，推出循环
}
运行结果：
------------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]