最佳组合算法

BenBear

可以用动态规划，计算出所有可能的结果，再取适当的。

bombzhao

思路却是应该是动态规划，但是现在如果让这一段程序在单片机中间运行呢？采用复杂的算法单片机不可能运算出来的！

RobinHoo

大概想了一下。
1、讲所有的数排序从大到小。
2、讲给定的数从排序数组第一个开始比较，得到第一个小于给定数的值，将其和给定数差作为第二给定数，重复步骤2，直到无法在数组中找出给定数。

RobinHoo

procedure seek()
read_array();
sort_array(desc);
read(given_num);
printf("%d=",given_num);
while (given_num>0)
{
     for(i=0;i<array_len;i++)
    {
        if array(i)<=given_num break;
    }
    if (i!=array_len && array(i)<=given_num)
    {
           printf("%d ",array(i));
           given_num-=array(i);
     }
}
printf("\n");

justicezyx

组合问题也许是算法当中最难的一类问题了。。。

arden1019

查表吧，反正也只有100以内的数，最多使用100个数组...如果你的单片机能放得下这100个数组。。

RobinHoo

对了我给的近似算法。会出现下面例外。
假设我的算法求出解序列a0,a1,a2...,an(降序数列)，原数列为list[0]....list[n](降序数列)。并有sum(a[i])+t=K(K是给定数)。从我的算法可以知道t比小于list[n]，有可能存在a[x]<list[i]+list[j]<=a[x]+t。那么list[i],list[j]将取代a[x]。反复应用取代，得出最优解。

ArXoR

很朴素的背包问题了,集合{s0,s1,s3...sn},给定的目标数m,
复杂度O(n*(m+min(m,max{si})))=O(nm)
200个位就行了,如果要记录解,就多一个大小200的数组

RobinHoo

发个测试版的

1. #include <stdio.h>
   
2. #include <ctype.h>
   
3. #include <math.h>
   
4. #include <stdlib.h>
   
5. #include <string.h>
   
6. float list[]={47,33,22,22,10,5,4.7,7.2};
   
7. int *result=NULL,*test=NULL;
   
8. int list_size=8,result_size=0,test_size=0;
   
9. float given_num,t,k;
   
10. int i,j;
    
11. int comp( const void *arg1, const void *arg2 )
    
12. {
    
13.         if (list[*(const int *)arg1]>list[*(const int *)arg2]) return -1;
    
14.         if (list[*(const int *)arg1]<list[*(const int *)arg2]) return 1;
    
15.         return 0;
    
16. }
    
17. 
    
18. int compF( const void *arg1, const void *arg2 )
    
19. {
    
20.         if (*(const int *)arg1>*(const int *)arg2) return -1;
    
21.         if (*(const int *)arg1<*(const int *)arg2) return 1;
    
22.         return 0;
    
23. }
    
24. 
    
25. int insertNum(int num)
    
26. {
    
27.         int *temp;
    
28.         int i;
    
29.         for(i=0;i<result_size;i++)
    
30.         if (result[i]==num) return 0;
    
31.         temp=(int *)calloc(result_size+1,sizeof(int));
    
32.         if (temp==NULL)
    
33.         {
    
34.                 fprintf(stderr,"memory overflow in insertNum, result size is %d\n",result_size);
    
35.                 free(result);
    
36.                 exit(1);       
    
37.         }
    
38.         memcpy(temp,result,sizeof(int)*result_size);
    
39.         temp[result_size++]=num;
    
40.         free(result);
    
41.         result=temp;
    
42.         qsort(result,result_size,sizeof(int),comp);
    
43.         return 1;
    
44.        
    
45. }
    
46. int insertTestNum(float num)
    
47. {
    
48.         int *temp;
    
49.         int i;
    
50.         for(i=0;i<test_size;i++)
    
51.         if (test[i]==num) return 0;
    
52.         for(i=0;i<result_size;i++)
    
53.         if (result[i]==num) return 0;
    
54.         temp=(int *)calloc(test_size+1,sizeof(int));
    
55.         if (temp==NULL)
    
56.         {
    
57.                 fprintf(stderr,"memory overflow in insertNum, test size is %d\n",test_size);
    
58.                 free(test);
    
59.                 free(result);
    
60.                 exit(1);       
    
61.         }
    
62.         memcpy(temp,test,sizeof(int)*test_size);
    
63.         temp[test_size++]=num;
    
64.         free(test);
    
65.         test=temp;
    
66.         qsort(test,test_size,sizeof(int),comp);
    
67.         return 1;
    
68.        
    
69. }
    
70. 
    
71. 
    
72. float sumArray(int * array,int array_size)
    
73. {
    
74.         int i;
    
75.         float sum;
    
76.         sum=0;
    
77.         for(i=0;i<array_size;i++) sum+=list[array[i]];
    
78.         return sum;
    
79. }
    
80. 
    
81. void showArray(int *array, int array_size)
    
82. {
    
83.         int i;
    
84.         float sum;
    
85.         sum=0;
    
86.         for(i=0;i<array_size;sum+=list[array[i]],i++) printf("%3.3f ",list[array[i]]);
    
87.         printf("total:%3.3f\n",sumArray(array,array_size));       
    
88. }
    
89. 
    
90. 
    
91. int main(void)
    
92. {
    
93.         float sum;
    
94.         qsort(list,list_size,sizeof(float),compF);
    
95.         given_num=k=50;
    
96.         for (i=0;i<list_size;i++)
    
97.         {
    
98.                 if (list[i]>k) continue;
    
99.                 if (insertNum(i)) k-=list[i];
    
100.         }
     
101.         showArray(result,result_size);
     
102.         i=0;
     
103.         while(i<result_size)
     
104.         {
     
105.                 if(test!=NULL) free(test);
     
106.                 test_size=0;
     
107.                 t=given_num-sumArray(result,result_size);
     
108.                 k=list[result[i]]+t;
     
109.                 for(j=result[i]+1;j<list_size;j++)
     
110.                 {
     
111.                         if (k<list[j]) continue;
     
112.                         if (insertTestNum(j)) k-=list[j];
     
113.                 }
     
114.                 sum=sumArray(test,test_size);
     
115.                 if (list[result[i]]<=t+sum && sum>list[result[i]])
     
116.                 {
     
117.                         for(j=0;j<test_size;j++)
     
118.                         {
     
119.                                 if (j>0) insertNum(test[j]);
     
120.                                 else result[i]=test[j];
     
121.                         }
     
122.                 }
     
123.                 if (k==0) break;
     
124.                 i++;
     
125.         }
     
126.         showArray(result,result_size);
     
127.         if (result!=NULL) free(result);
     
128.         if (test!=NULL) free(test);
     
129. }

复制代码