觉得这个题目还有点意思 就花了点时间做了下
这个题目的规模实在是大 别看就只有126个数据 但是问题搜索范围是2的126次方
没估算过 所有情况都一一遍历的话 需要多长时间 应该是需要很久的
这类运算量大的题目 保留中间计算结果 尽量减少重复计算的次数 应该是一个好的优化算法的思路
我在2楼的递归算法的基础上 做了3点改进
仍然是从大到小排序 从大数开始选择 但是每次递归改为求解剩余需要组合的值 比如sum=9 已经选择了 6 那么从6之后 求解能合成3的方法
具体改进的地方：
1. 向后搜索时 不是一一搜索 而是跳过比sum值大的值 因为他肯定不是有效组合 只要加上他就超了 就不用试了
2. 判断如果这之后所有的值都加起来的和比sum值要小 那么就终止本轮搜索 向前回溯 因为即使加上所有值 都组不成有效解
3. 保留中间过程的计算结果 比如在求解过程中 发现 在搜索sum=9时 从位置5往后没有可行解
那么下次再要搜索9时而且起始位置在5或之后 就根据这个信息直接结束递归并向前回溯
其实 起到真正效果的是 第3点 前两点的优化效果不是很明显
但是 不幸的是 经过求解发现 楼主给的2894是找不到有效组合的 有可能是真的没有可行解 不过结论仅供参考
下面是代码 发现bug 欢迎指出 不懂算法 纯属个人瞎编
编译器 mingw5，C编译器不支持内置bool 请修改代码中相应符号定义
程序代码：
#include <stdio.h>
#include <stdlib.h>
#define Compiler_CPP //编译器类型 判断是否支持内置bool类型
#define Display_ON //控制台显示开关 是否打开中间过程显示
#define IN_FILE "in.txt"
#define OUT_FILE "out.txt"
#define DATA_SIZE 9*14
#define SUM 2894
#ifdef Compiler_C
typedef enum{false, true} bool;
#endif
typedef enum{open, append, close} option;
typedef struct
{
bool flag;
int pos;
}feas; //可解标志 判断对于指定值在某个位置之后是否存在可行解
int g_dat[DATA_SIZE];
int g_cum[DATA_SIZE];
int g_res[DATA_SIZE];
feas g_midres[SUM+1];
void input(void);
void init(void);
void output(option outmode, int num);
bool solve(int sum, int datpos, int respos);
int main()
{
input();
init();
output(open, 0);
if(solve(SUM, 0, 0))
printf("\rAll cases are tried and at most one solution is found.\n");
else
printf("\rAll cases are tried and none solution is found.\n");
output(close, 0);
return 0;
}
void input(void)
{
int i;
FILE *fp;
if((fp=fopen(IN_FILE, "r")) == NULL){
printf("Open file %s failed!\n", IN_FILE);
exit(1);
}
for(i = 0; i < DATA_SIZE; i++)
fscanf(fp, "%d", g_dat+i);
fclose(fp);
}
static int cmp_lt(const void *p1, const void *p2)
{
return (*(int*)p2 - *(int*)p1);
}
void init(void)
{
int i;
qsort(g_dat, DATA_SIZE, sizeof(int), cmp_lt);
g_cum[DATA_SIZE-1] = g_dat[DATA_SIZE-1];
for(i = DATA_SIZE-2; i >= 0; i--)
g_cum[i] = g_cum[i+1] + g_dat[i];
for(i = 0; i < SUM+1; i++)
g_midres[i].flag = true;
}
void output(option outmode, int num)
{
int i;
static FILE *fp;
static int cnt = 0;
switch(outmode){
case open:
goto pro_open;
case append:
goto pro_append;
case close:
goto pro_close;
default:
return;
}
pro_open:
if((fp=fopen(OUT_FILE, "w"))==NULL){
printf("Open file %s failed!\n", OUT_FILE);
exit(1);
}
fprintf(fp, "[ORDER]\t[Feasible Solutions(sum is %d)]\n", SUM);
return;
pro_append:
fprintf(fp, " %05d\t ", ++cnt);
for(i = 0; i < num; i++)
fprintf(fp, "%4d\t", g_res[i]);
fprintf(fp, "\n");
#ifdef Display_ON
printf("\rORDER %d: ", cnt);
for(i = 0; i < num; i++)
printf("%4d ", g_res[i]);
printf("\n");
for(i = 0; i < num; i++)
printf("%4d ", g_res[i]);
#endif
return;
pro_close:
fclose(fp);
return;
}
static int next(int pos, int val)
{
while(pos<DATA_SIZE && g_dat[pos]>val)
pos++;
return pos;
}
bool solve(int sum, int datpos, int respos)
{
bool is_solved;
int nextpos;
if(sum == 0){
if(respos == 0)
return false;
output(append, respos);
return true;
}
else if(sum <= g_cum[datpos]){
is_solved = false;
nextpos = next(datpos, sum);
while(nextpos < DATA_SIZE){
#ifdef Display_ON
printf("%4d ", g_dat[nextpos]);
#endif
g_res[respos] = g_dat[nextpos];
if(g_midres[sum-g_dat[nextpos]].flag ||
g_midres[sum-g_dat[nextpos]].pos > nextpos+1){
if(solve(sum-g_dat[nextpos], nextpos+1, respos+1)){
is_solved = true;
}
else{
g_midres[sum-g_dat[nextpos]].flag = false;
g_midres[sum-g_dat[nextpos]].pos = nextpos+1;
}
}
#ifdef Display_ON
printf("\b\b\b\b\b");
#endif
while(nextpos<DATA_SIZE && g_dat[nextpos]==g_res[respos])
nextpos = next(nextpos+1, sum);
}
return is_solved;
}
else return false;
}
好难，上面那些程序好难看懂