部分和查找/部分和组分配 [英] Partial sum lookup / partial sum set assignment
问题描述
我有以下问题需要解决。由于输入我有2个十进制阵列。他们两人的元素之和相等。实际工作的问题是从一个阵列到第二个由部分和分配值 - 如果从一个阵列的一些元件是任意数量从第二阵列元素的总和 - 他们应该被分配到彼此
I have following problem to solve. As as input i have 2 decimal arrays. Sum of elements of both of them is equal. Actuall problem is to assign values from one array to second one by partial sums - if some element from one array is a sum of any number of elements from second array - they should be assigned to each other.
样品1:
数组1:25.0,25.0,50.0,50.0 ARRAY2:50.0,100.0
Array1: 25.0, 25.0, 50.0, 50.0 Array2: 50.0, 100.0
预期结果:50.0是25.0和25.0总和,100.0是50.0和50.0
总和
(0-> 0,1; 1> 2,3)
Expected result: 50.0 is sum of 25.0 and 25.0, 100.0 is a sum of 50.0 and 50.0
(0->0,1; 1->2,3)
样品2:
数组1:20.0,70.0,80.0,130.0 ARRAY2:100.0,200.0
Array1: 20.0, 70.0, 80.0, 130.0 Array2: 100.0, 200.0
预期结果: 100 = 20 + 80,200 = 70 + 130(0-> 0,2; 1> 1,3)
Expected result: 100 = 20+80, 200 = 70+130 (0->0,2; 1->1,3)
想法是返回指定数组索引和返回为少assingments越好。
Idea is to return assigned array element indexes and return as less assingments as possible.
推荐答案
这就是所谓的子集和问题。
不幸的是,这是NP完全问题,这意味着你必须检查所有可能的组合。
Unfortunately this is NP-complete, meaning you have to check all possible combinations.
不过,如果你的问题是只有少量部分和(如你的例子),那么穷举了。
However, if your problem is only has a small quantity of partial sums (such as your examples) then brute force away.
伦是正确的,并非所有的NP完全问题需要检查所有可能的组合。
不过,我相信子集和是一个没有。
Moron is correct, not all NP-complete problem require checking all possible combinations.
However I believe subset sum is one that does.
这篇关于部分和查找/部分和组分配的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!