学步园

/*
编译环境：
gcc (GCC) 3.2 20020903 (Red Hat Linux 8.0 3.2-7)
Copyright (C) 2002 Free Software Foundation, Inc.
Author：NinGoo
*/

#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]