在CSDN论坛看到有人问了这个问题，还挺有趣的，关键是他这个的数据量是非常大
原链接http://bbs.csdn.net/topics/391897373
这一题肯定不能用枚举（其实这样的题都不用枚举），一个是时间太长了，第二就是储存容量也不够，这一题大概1e+20左右的大小，跑半天不说，还是会溢出的，即使剪枝
我一开始想到用分治的方法，后来想了一下21个数实在是太大了，而且他的数据量也不是小，是120+个数，所以我想到了用背包，其实这类的问题都可以用背包问题来解决的。
但是他这一题不是问选多少个物品小于什么重量找最大价值的题，那我们就改一下，把选的物品的个数变成价值，而且除非能直接到达固定值，否则最大选的个数就一直是select-1
我自己做的时间复杂度也是挺大的，因为我是对总量进行背包的，所以时间复杂度是0（C*P*N），在我的机子跑79S。。。说实话很慢
如果要优化的话，可以把数拆分成一个一个区域，然后再背包，这样包容量可以减少好几个数量级，跑起来相当快了
#include <iostream> #include <functional> #include <algorithm> #include <time.h> #define SIZE 125 #define MAX 6531127 using namespace std; static int input[SIZE] = { 55000, 55000, 63500, 96120, 97000, 102350, 102350, 132510, 135370, 140000, 144000, 166800, 167530, 169800, 178300, 178300, 178800, 179300, 181000, 181000, 181000, 181000, 181000, 181000, 181000, 182200, 183500, 185684, 188800, 188800, 189800, 190800, 190800, 190800, 195684, 198000, 199626, 199626, 199800, 199800, 199900, 201000, 208700, 209800, 209800, 209800, 209800, 209800, 219000, 219000, 219000, 219000, 219800, 220000, 220000, 220000, 220130, 225600, 228000, 228000, 229434, 229800, 229800, 229800, 229800, 235000, 238800, 240000, 240900, 244800, 247800, 248000, 249800, 249800, 249800, 249800, 249800, 249800, 249800, 249800, 250000, 250000, 250000, 250000, 257000, 260800, 279800, 279800, 279800, 279800, 280340, 285000, 295000, 295000, 295000, 298000, 299000, 300000, 300000, 300000, 313701, 328897, 337300, 345000, 350000, 350000, 350000, 350064, 350064, 350064, 350064, 350064, 429800, 430290, 440154, 472200, 472200, 487305, 500500, 506300, 512226, 544110, 749000, 820000, 1100000 }, goal_select = 21; static struct _set { char _num_sum[5], _select[5][21]; int rep; }bag1[MAX + 1], bag2[MAX + 1], *tmp, *dp1, *dp2; void Print_Select(struct _set *goal,const int rep) { int pos_stop = goal[MAX]._num_sum[rep]; cout << "The items are :" << endl; for (int i = 0; i < pos_stop; i++) cout << goal[MAX]._select[rep][i] + 1 << ": " << input[goal[MAX]._select[rep][i]] << endl; } void Copy(const int m1, const int m2) { memcpy(dp2[m2]._num_sum, dp1[m1]._num_sum, sizeof(dp2[m2]._num_sum)); memcpy(dp2[m2]._select, dp1[m1]._select, sizeof(dp2[m2]._select)); dp2[m2].rep = dp1[m1].rep; } int Max(const int x, const int y) { return x > y ? x : y; } void Merge_Bound(struct _set *pos1, struct _set *pos2, struct _set *goal,const int stuff) { int ptr_dp1 = 0, ptr_dp2 = 0, tmp_sum, tmp_rep = 0; int up_bound = Max(pos1->_num_sum[pos1->rep - 1], pos2->_num_sum[pos2->rep - 1]) + 1; for (int i = 1; i <= up_bound; i++) { if (pos1->rep != 0//0代表不合法 && (pos1->_num_sum)[ptr_dp1] + 1 <= goal_select - 1 && (pos1->_num_sum)[ptr_dp1] + 1 == i) { (goal->_num_sum)[tmp_rep] = tmp_sum = (pos1->_num_sum)[ptr_dp1] + 1; memcpy((goal->_select)[tmp_rep], (pos1->_select)[ptr_dp1], sizeof((goal->_select)[tmp_rep])); (goal->_select)[tmp_rep][tmp_sum - 1] = stuff - 1; ptr_dp1++; tmp_rep++; } else if (pos2->rep != 0 && (pos2->_num_sum)[ptr_dp2] == i) { (goal->_num_sum)[tmp_rep] = (pos2->_num_sum)[ptr_dp2]; memcpy((goal->_select)[tmp_rep], (pos2->_select)[ptr_dp2], sizeof((pos2->_select)[ptr_dp2])); ptr_dp2++; tmp_rep++; } } goal->rep = tmp_rep; } bool Search(void) { int pos, num_sum; dp1[0].rep = 1; for (int i = 1; i <= SIZE; i++) { dp2[0].rep = 1; for (int j = 1; j < input[i - 1]; j++) Copy(j, j); for (int j = input[i - 1]; j <= MAX; j++) { if (j == MAX && dp1[MAX - input[i - 1]]._num_sum[dp1[MAX - input[i - 1]].rep - 1] + 1 == goal_select)//直接输出 { Copy(MAX - input[i - 1], MAX); pos = dp1[MAX - input[i - 1]].rep - 1; dp2[MAX]._num_sum[pos]++; num_sum = dp2[MAX]._num_sum[pos]; dp2[MAX]._select[pos][num_sum - 1] = i - 1; Print_Select(dp2, dp2[MAX].rep - 1); return true; } Merge_Bound(&dp1[j - input[i - 1]], &dp1[j], &dp2[j], i); } tmp = dp1; dp1 = dp2; dp2 = tmp; } return false; } int main(void) { dp1 = bag1; dp2 = bag2; time_t t1 = clock(); if (Search()) cout << "SUCCESS" << endl; else cout << "FAIL" << endl; time_t t2 = clock(); cout << t2 - t1 << "ms" << endl; system("pause"); return EXIT_SUCCESS; }