部分和查找/部分和组分配 [英] 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屋！