package.cpp

背包问题的回溯法,用回溯法解决背包问题,区别于其他算法

#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时，所有可能的组合都考察完毕，推出循环
}