gxqcn 发表于 2019-11-12 14:54
说白了，就是将一组数据，取一部分出来，使之总和尽可能接近某个确定值
换个说法可能更准确些，有限数据的组合情况是有限的，最接近某个确定值的数肯定存在（正偏离或负偏离）。现在的问题是如何确认自己找到的较好解是最优解。当然全组合出来肯定就能看出是不是最优解，是否能通过其他方式确定算出的解就是最优解。
.·.·. 发表于 2019-11-12 23:21
这不是NPC吗？
题目等价于找到一个给定集合的子集，子集里全体元素和与定值之差最小
注意：是差值最小，不是等于0.若是等于0，很显然是NPC问题。但这个有些差别。
.·.·. 发表于 2019-11-12 23:21
这不是NPC吗？
题目等价于找到一个给定集合的子集，子集里全体元素和与定值之差最小
你还是没理解题意。比如说求组合值最接近15的组合，此时的结果是.组合中没有比这更接近的。（注意最接近不是要求一定等于，当组合中没有等于时只能选最接近的。）
若是求中组合值最接近15的组合，此时结果是.最接近可以理解为偏离最小，如16比13更接近15.
aimisiyou 发表于 2019-11-13 01:41
你还是没理解题意。比如说求组合值最接近15的组合，此时的结果是.组合中没有 ...
比如说中最接近0的组合
如果算法已经约定了至少要选择一个数字，那么我们只能选，于是我们知道的任意非空子集元素和非零（后者是一个NPC问题）
如果允许选择空集，那么换一种玩法
对集合，先选出其中的元素1，发现不是0
验证集合中最接近-1的组合，发现是[]，并不等于-1，这证明了所有含有元素1的子集元素和都不是0
递归地验证是否有子集满足元素和为0
前者只需要执行1次算法，而后者只需要n次，都是多项式时间完成的
而程序解决了一个NPC问题
唯一的可能是，算法就是NP-hard的算法。
.·.·. 发表于 2019-11-13 02:51
比如说中最接近0的组合
如果算法已经约定了至少要选择一个数字，那么我们只能选，于是我们 ...
忘了说明数组元素都是正数。组合的和值（最接近的固定值）在元素最小值和所有累加值之间。
(FEN_2 '(8 4 2 1) 0)
(15 8 (8))
(FEN_2 '(8 4 2 1) 17)
(15 15 (1 2 8 4))
只是较好解，不是最优解。鉴定完毕。
(fen_2'(35 33 31 27 24 22 17 15 1198 5 ) 0)
(237 116 (11 15 17 22 27 24))
最优的解是（3533 31 155）和（27 24 22 17 11 9 8），和值分别为119和118。
由于组合算法太吓人了，想通过排序，比较，快速的找到近优解。
aimisiyou 发表于 2019-11-12 16:04
理解中的背包算法是首先挑选价值最大的物品，使得物品容量不超过背包容量，物品价值总额最大。这个问题怎 ...
一下子混淆了，应当是动态规划。
从大到小，逐个数字分支为选或不选。合并等和方案，而且剔除不可变得更好的方案。
既然数据可以转移可以交换，就完全可以忽略开始分组。第一步把第二组元素全部移到第一组；第二步把最好方案之外的元素移到第二组。
所以下面只考虑如何计算最好方案。
合并数据为。
和为607，希望差为17。所以划分数据和最好是295与312
{{100,92,76,63,50,10},{71,45,33,20,15,13,9,6,4},13}//Function[{S1,S2,\},S1~Join~S2//Sort//Reverse//{#,Solve[{Subscript+Subscript==Total[#],Subscript-Subscript==\}]//First//Subscript/.#&}&]@@#&//Function[{AllDataList,Part1Total},Fold(Append[#,AllDataList[]]&/@B)//GatherBy[#,Total]&//#[]&//SortBy[#,Total]&//{Select[#,Total[#]+Total]]<Part1Total&],#,(Select[#,Total[#]>Part1Total&])}&//{If[#[]=={},{},#[]],Complement[#[],#[],#[]],If[#[]=={},{},#[]]}&//Join@@#&],{{}},Range]]//SortBy[#,Abs-Part1Total]&]&//First//{#//Sort,Complement}&]@@#&//(Print]]-Total[#[]]];#)&
17
{{6, 50, 71, 76, 92}, {4, 9, 10, 13, 15, 20, 33, 45, 63, 100}}
补充内容 (2019-11-15 00:03):
请管理员把代码替换到以下内容。
改动1，原代码我用了调试的差值13，但发了差值17的结果。
改动2，新代码增加中间判断，有完全结果就停止分支搜索。
{{100,92,76,63,50,10},{71,45,33,20,15,13,9,6,4},17}...
补充内容 (2019-11-15 00:04):
代码字数太多，只好再开一层。
这是伪多项式算法，取决于数据的“密度”。如果数据足够“密集”，和相等的中间方案更多，就能充分合并搜索分支。否则就佛系搜索，按下计算，等缘分到那天自然有结果。