Поиск частичной суммы / присвоение частичной суммы

Question

У меня есть следующая проблема, чтобы решить.В качестве входных данных у меня есть 2 десятичных массива.Сумма элементов обоих из них равна.На самом деле проблема состоит в том, чтобы присвоить значения из одного массива второму частичными суммами - если какой-либо элемент из одного массива является суммой любого количества элементов из второго массива - они должны быть присвоены друг другу.

Sample1:

Массив 1: 25,0, 25,0, 50,0, 50,0 Массив 2: 50,0, 100,0

Ожидаемый результат: 50,0 - это сумма 25,0 и 25,0, 100,0 - это сумма 50,0 и 50,0
(0-> 0,1; 1-> 2,3)

Образец 2:

Массив 1: 20,0, 70,0, 80,0, 130,0 Массив 2: 100,0, 200,0

Ожидаемый результат:100 = 20 + 80, 200 = 70 + 130 (0-> 0,2; 1-> 1,3)

Идея состоит в том, чтобы возвращать назначенные индексы элементов массива и возвращать как можно меньше заданий.

Answer 1

Это называется проблемой суммы подмножеств .

К сожалению, это NP-полная, то есть вы должны проверить все возможные комбинации.

Однако, если ваша проблема имеет только небольшое количество частичных сумм (например, ваших примеров), то откажитесь от грубой силы.

---

Морон верен, не все NP-полные задачи требуют проверки всех возможных комбинаций.
Однако я считаю, что сумма подмножества равна .