两数组通过转移、交换数据使得差值最接近固定数值

aimisiyou

gxqcn 发表于 2019-11-12 14:54
说白了，就是将一组数据，取一部分出来，使之总和尽可能接近某个确定值

换个说法可能更准确些，有限数据的组合情况是有限的，最接近某个确定值的数肯定存在（正偏离或负偏离）。现在的问题是如何确认自己找到的较好解是最优解。当然全组合出来肯定就能看出是不是最优解，是否能通过其他方式确定算出的解就是最优解。

aimisiyou

.·.·. 发表于 2019-11-12 23:21
这不是NPC吗？
题目等价于找到一个给定集合的子集，子集里全体元素和与定值之差最小

注意：是差值最小，不是等于0.若是等于0，很显然是NPC问题。但这个有些差别。

aimisiyou

.·.·. 发表于 2019-11-12 23:21
这不是NPC吗？
题目等价于找到一个给定集合的子集，子集里全体元素和与定值之差最小

你还是没理解题意。比如说[3 11 22 44 65 67]求组合值最接近15的组合，此时的结果是[3  11].组合中没有比这更接近的。（注意最接近不是要求一定等于，当组合中没有等于时只能选最接近的。）
若是求[5 11 22 44 65 67]中组合值最接近15的组合，此时结果是[5,11].最接近可以理解为偏离最小，如16比13更接近15.

.·.·.

aimisiyou 发表于 2019-11-13 01:41
你还是没理解题意。比如说[3 11 22 44 65 67]求组合值最接近15的组合，此时的结果是[3  11].组合中没有 ...

比如说[1,2,4,8]中最接近0的组合
如果算法已经约定了至少要选择一个数字，那么我们只能选[1]，于是我们知道[1,2,4,8]的任意非空子集元素和非零（后者是一个NPC问题）

如果允许选择空集，那么换一种玩法
对集合[1,2,4,8]，先选出其中的元素1，发现不是0
验证[2,4,8]集合中最接近-1的组合，发现是[]，并不等于-1，这证明了所有含有元素1的子集元素和都不是0
递归地验证[2,4,8]是否有子集满足元素和为0

前者只需要执行1次算法，而后者只需要n次，都是多项式时间完成的
而程序解决了一个NPC问题
唯一的可能是，算法就是NP-hard的算法。

aimisiyou

.·.·. 发表于 2019-11-13 02:51
比如说[1,2,4,8]中最接近0的组合
如果算法已经约定了至少要选择一个数字，那么我们只能选[1]，于是我们 ...

忘了说明数组元素都是正数。组合的和值（最接近的固定值）在元素最小值和所有累加值之间。
(FEN_2 '(8 4 2 1) 0)
(15 8 (8))


(FEN_2 '(8 4 2 1) 17)
(15 15 (1 2 8 4))

aimisiyou

只是较好解，不是最优解。鉴定完毕。
(fen_2  '(35 33 31 27 24 22 17 15 11  9  8 5 ) 0)
(237 116 (11 15 17 22 27 24))

最优的解是（35  33 31 15  5）和（27 24 22 17 11 9 8），和值分别为119和118。


由于组合算法太吓人了，想通过排序，比较，快速的找到近优解。

zeroieme

aimisiyou 发表于 2019-11-12 16:04
理解中的背包算法是首先挑选价值最大的物品，使得物品容量不超过背包容量，物品价值总额最大。这个问题怎 ...

一下子混淆了，应当是动态规划。
从大到小，逐个数字分支为选或不选。合并等和方案，而且剔除不可变得更好的方案。

zeroieme

既然数据可以转移可以交换，就完全可以忽略开始分组。第一步把第二组元素全部移到第一组；第二步把最好方案之外的元素移到第二组。

所以下面只考虑如何计算最好方案。

zeroieme

合并数据为[100, 92, 76, 71, 63, 50, 45, 33, 20, 15, 13, 10, 9, 6, 4]。
和为607，希望差为17。所以划分数据和最好是295与312

1. {{100,92,76,63,50,10},{71,45,33,20,15,13,9,6,4},13}//Function[{S1,S2,\[CapitalDelta]},S1~Join~S2//Sort//Reverse//{#,Solve[{Subscript[x, 1]+Subscript[x, 2]==Total[#],Subscript[x, 1]-Subscript[x, 2]==\[CapitalDelta]}]//First//Subscript[x, 2]/.#&}&]@@#&//Function[{AllDataList,Part1Total},Fold[Function[{B,i},B\[Union](Append[#,AllDataList[[i]]]&/@B)//GatherBy[#,Total]&//#[[All,1]]&//SortBy[#,Total]&//{Select[#,Total[#]+Total[AllDataList[[i+1;;-1]]]<Part1Total&],#,(Select[#,Total[#]>Part1Total&])}&//{If[#[[1]]=={},{},#[[1,-1;;-1]]],Complement[#[[2]],#[[1]],#[[3]]],If[#[[3]]=={},{},#[[3,1;;1]]]}&//Join@@#&],{{}},Range[Length[AllDataList]]]//SortBy[#,Abs[Total[#]-Part1Total]&]&//First//{#//Sort,Complement[AllDataList,#]}&]@@#&//(Print[Total[#[[2]]]-Total[#[[1]]]];#)&

复制代码

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，新代码增加中间判断，有完全结果就停止分支搜索。

[code]{{100,92,76,63,50,10},{71,45,33,20,15,13,9,6,4},17}...

补充内容 (2019-11-15 00:04):
代码字数太多，只好再开一层。

zeroieme

这是伪多项式算法，取决于数据的“密度”。如果数据足够“密集”，和相等的中间方案更多，就能充分合并搜索分支。否则就佛系搜索，按下计算，等缘分到那天自然有结果。