装书包问题：

从不同重量书中选任意本装入书包，刚好达到书包限重;

1,mony[ ]存放多种不同重量的书;

2,书包限重sum;

3,从mony[ ]中选取任意组合，使总重恰好等于sum;

4,输出所有可能组合;

#include
     
      #include
      
       int sum=10;//计算mony中所有能组成sum的元素组合，元素不得重复，输出所有组合情况//start为遍历数组mony[]的起始位置：void FUN(int mony[],int len,int ret[],int start){
   //len是mony长度        if(ret[len]>sum) return;        if(ret[len]==sum){
   //ret[]最后一位存和数                int i=0;                for(;i<=len;i++){                        if(ret[i]!=0){                                printf("----%d",ret[i]);                        }                }                printf("\n");                return;        }        int i=start;        for(;i
      
     

输出结果如下：

xu@xu-ThinkPad-X61:~/algorithm$ ./exe beibaobuchfu.c

----1----3----2----4----10

----1----5----4----10

----3----5----2----10

 

算法非递归实现方法：

1.举个栗子：inp[ ]={1,2,3,4}，sum=6,计算组成sum所有可能不重复元素组合，输出最小个数值;

2,ret[sum+1]存放结果：当{1,2,3,4}中任意k个元素可以组成i时（比如2和4能组成6，此时k=2），ret[i]存放元素个数k;

3,ret[sum+1]存放的值就是可以组成sum的组合中元素个数最小的个数值;

 

#include
     
      #include
      
       void FUN(int inp[],int len, int*ret, int lenret){        int i=0;        for(;i
       
        ret[j+tmp]?                                                ret[j+tmp]:(ret[j]+1));                        }                }        }}int main(){        int input[]={
   1,2,3,4};        int sum=6;        int result[6+1]={
   1};        FUN(input,4, result, sum+1);        int k=0;        for(;k<7;k++){                printf("%d++",result[k]);        }        return 0;}
       
      
     

输出结果：

xu@xu-ThinkPad-X61:~/algorithm$ ./exe suibian.c

1++2++2++2++2++3++3++

说明最少3个元素组成6;