求教C语言背包问题做法

ScropJr1

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

求C语言思路...

秀丽江山

你说的什么东西。。。你自己看得懂吗

ANDES

1. #include <stdio.h>
   
2. #define size 20
   
3. struct stacks
   
4. {
   
5. int data[size];
   
6. int top;
   
7. }stack;void main()
   
8. {
   
9.   int w[size];
   
10.   int V;
    
11.   int k=0;   
    
12.   int i=0;
    
13.   int j=1;
    
14.   int number;
    
15.   int s=0;
    
16.   
    
17.   printf("\n请输入可供选择装入物品的个数：");
    
18.   scanf("%d",&number);
    
19.   printf("\n请输入各件物品的体积：");
    
20.   for(i=0;i<number;i++)
    
21.   scanf("%d",&w[i]);
    
22.   for(i=0;i<number;i++)
    
23.   s=s+w[i];
    
24.   printf("\n可供选择的物品的总体s=%d\n",s);
    
25.   printf("\n请输入背包的总体积：");
    
26.   scanf("%d",&V);
    
27.   if(V<0||V>s)
    
28.   printf("\n输入背包体积错误");
    
29.   printf("\n");
    
30.   for(i=0;i<number;i++)
    
31.   stack.data[i]=0;
    
32.   stack.top=0;
    
33.   do
    
34.   {
    
35.   while(V>0&&k<=number)
    
36.   {
    
37.   if(V>=w[k])
    
38.   {
    
39.   stack.data[stack.top]=k;
    
40.   stack.top++;
    
41.   V-=w[k];
    
42.   }
    
43.   k++;
    
44.   }
    
45.   if(V==0)
    
46.   {
    
47.   printf("第%d个符合条件的解：",j);
    
48.   for(i=0;i<stack.top;i++)
    
49.   {
    
50.   printf("%d ",w[stack.data[i]]);
    
51.   }
    
52.   j++;
    
53.   printf("\n");
    
54.   }
    
55.   k=stack.data[--stack.top];
    
56.   stack.data[stack.top]=0;
    
57.   V+=w[k];
    
58.   k++;
    
59.   }while(!(stack.top==0&&k==number));}
    

复制代码