简单背包

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95

#include <stdio.h> #include <windows.h> #define size 50 struct stacks { int data[size]; int top; } stack; void backpack(int number,int V,int w[]){ int i,j=1,k=0; int flag=0; do { while (V > 0 && k <= number) { if (V >= w[k]) { stack.data[stack.top] = k;//第 k 个物品的体积下标 stack.top++; V -= w[k]; } k++; } if (V == 0) { flag=1; printf("第%d 个符合条件的解：", j); for (i = 0; i < stack.top; i++) { printf("%d ", w[stack.data[i]]); } j++; printf("\n"); } //k 满时回溯 k = stack.data[--stack.top]; stack.data[stack.top] = 0; V += w[k]; k++; } while (!(stack.top == 0 && k == number)); if(!flag){ printf("背包无解！\n"); } } void judge(int number,int V,int w[]){ int i,s = 0; for (i = 0; i < number; i++) s = s + w[i]; if(V > s){ printf("背包无解！\n"); exit(0); } if(V==s){ printf("只有一个符合条件的解：%d\n", V); exit(0); } } int main() { int w[size]; int V; int i = 0; int j = 0; int number; printf("\t **简单背包问题**\n\n"); printf("\n 请输入可供选择装入物品的个数：\n"); scanf("%d", &number); printf("\n 请输入各件物品的体积：\n"); for (i = 0; i < number; i++) scanf("%d", &w[i]); //排序 for(i=0;i<number;i++) for(j=i+1;j<number;j++) if(w[i]>w[j]){ w[i]=w[i]^w[j]; w[j]=w[i]^w[j]; w[i]=w[i]^w[j]; } printf("\n 请输入背包的总体积：\n"); scanf("%d", &V); while(V < 0){ printf("输入背包体积错误！重新输入！\n"); scanf("%d",&V); } judge(number,V,w); //初始化栈 for (i = 0; i < number; i++) stack.data[i] = 0; stack.top = 0; backpack(number,V,w); return 0; }