Ka的递归编程练习 Part6|简单背包问题，拒绝动规从我做起

 1 #include <stdio.h>
 2 #define M 10 
 3 int w[M]={1,3,5,7,9,11,13,15,17,19};
 4 int backpack(int n,int s) //n代表容量，s代表物品个数
 5 {
 6     if(n==0)    return 1;   //如果刚好装完，此支线满足条件，返回1 
 7     else if(n<0||s<=0) return 0;  //此条支线出现了装一个重量超过限额或全部用完也未装满，返回0 
 8     else if(backpack(n-w[s-1],s-1)==1)  //此条支线传来好消息，输出并往上一层返回1 
 9     {                                   //此时注意下表是s-1，否则将越界 
10         printf("bp:No.%d,weight %d.
",s,w[s-1]);
11         return 1;
12     }
13     else return backpack(n,s-1);  //如果这个物品并未出现以上情况，就跳过，n不变 
14 } 
15 int main()
16 {
17     if(backpack(80,M)!=1) printf("No result.");  //当成功时返回1，所以不返回1时输出无解。 
18     return 0;
19 }

差不多就是上面这样了，注释那么多就不多解释了吧~

问题的话：有一个背包，容量为n，现有s件物品，重量为w1,w2,w3,...,ws，求一组刚好能放完背包的组合解。如

w为{1,3,5,7,9}，n为11时，解为w1:1 w2:3 w4:7