数据结构C语言实现的背包问题

#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 i,j=0,k=0; struct Stack { //栈 int s[N]; int top; } stack; //初始化栈 for(i=0;i<N;i++) stack.s[i]=0; stack.top=0; do{ while(T>0&&k<=N) { if(T>=w[k]) { //符合条件的背包进栈 stack.s[stack.top++]=k; T-=w[k]; } k++; //不符合则考察下一个背包 } if(T==0){ //找到一种方法，输出 printf("\n",j); for(i=0;i<stack.top;i++){ printf("(%d) ",w[stack.s[i]]); } j++; printf("\n"); } k=stack.s[--stack.top]; //找不到方法，则前一个入栈的背包出栈，继续考察下一个背包 stack.s[stack.top]=0; T+=w[k]; k++; }while(!(stack.top==0&&k==N)); //当栈空且k==N时，所有可能的组合都考察完毕，退出循环 }