C Найти меньшее различие между двумя стеками

Question

Если у меня есть два stacks, которые я должен поместить элементы, которые исходят от array, и я должен найти рекурсивный способ поместить элементы, которые подчиняются правилу нахождения меньшей разницы между сумма двух стеков ...

Как это:

values[5] ={1,2,3,4,5} 

Stack1 = 4,3 

Stack2 = 5,2,1 

or 

Stack2 = 4,3 

Stack1 = 5,2,1 
Difference = between 1 and 2 = 1 

Можете ли вы помочь мне найти способ сделать это рекурсивно? или, по крайней мере, понять, как это сделать?

Answer 1

Это в основном partition problem, который является NP-Complete.
Вы пытаетесь разделить массив w на два подмножества (стеки в вашем случае не имеют значения), чтобы их сумма была равна в лучшем случае или как можно ближе к ней.

Нет никакого известного полиномиального решения для него, но если числа являются довольно маленькими целыми числами - есть хороший dynamic programming solution, чтобы быстро решить эту проблему.

Жадный подход (помещение наивысшего элемента в стек с нижней суммой и повторение) является приближением, которое в худшем случае будет |SUM|/2 хуже оптимального решения.

EDIT: Динамический подход программирования в основном рекурсивный по своей природе:

base: 
f(0,i) = true 
f(x,0) = false (x > 0) 
step: 
f(x,i) = f(x-arr[i],i-1) OR f(x,i-1) 

Invoke с f(SUM/2,n) найти, если есть оптимальное решение.
Теперь подумайте:

1. Как из этого вы можете найти 'ближайший' решение, если f(SUM/2,n) = false?
2. Как вы можете изменить это решение, чтобы также дать вам индексы желаемого решения, а не только логический ответ?

Примечание:

• Другой рекурсивный подход был бы для проверки всех возможных подмножеств массива (есть 2^п из них), и выбрать тот, который сводит к минимуму разницу до |SUM|/2