排列组合算法，要求从一堆数中任取m个数组合使得m个数的和最接近某个数

Question

比如某个数组有元素如下 ：
元素133有2个，121有4个，108 有2个，58有14个 ，115有6个

要求从中取任意个数使得他们的和最接近600，所有元素要求全部组合完。
比如：121取4个加上108取1个

组合1：121*4+108*1=592 ---121 取完了，108还剩1个
组合2：133*1+115*3+58*2=594--
组合3：133*1+115*3+58*2=594--133取完了，115 取完了，58还剩10 个
组合4：58*10=580 --全部取完

要求：（600- 组合1的和）+（600- 组合2的和）+
（600- 组合3的和）+（600- 组合4的和）在所有的组合方案中
值最小为最优方案

Answer 1

典型的组合问题，解法有递归、回溯等等递归法较简单，代码如下： void combine(int a[], int n, int m, int b[], int M); 参数：a 存放候选数字n 总项数m 取出项数b 存放选出结果M = m

#include "stdio.h"#define MAX 100 void combine(int a[], int n, int m, int b[], int M); int main(void){ int i; int a[MAX], b[MAX]; for (i = 1; i < 100; i++) a[i - 1] = i; combine(a, 5, 4, b, 4);} void combine(int a[], int n, int m, int b[], int M){ int i, j; for (i = n; i >= m; i--) { b[m - 1] = i - 1; if (m > 1) combine(a, i - 1, m - 1, b, M); else { for (j = M - 1; j >= 0; j--) printf("%d ", a[b[j]]); printf("\n"); } }}

其他方法可查阅相关资料。