Алгоритм подкомбинации динамического программирования

Question

Я работаю над некоторыми материалами для динамического программирования. Мне нужно придумать, как должны быть разделены подзадачи, выработать базовый случай и придумать рекурсивную формулу.

Приведенные n положительных целых чисел a1, a2, ..., an, число k и цель W, мы хотим выбрать подмножество T с точно k элементами, сумма которых ближе всего к W. Каждый элемент может быть выбран только один раз. Определите подзадачу с тремя параметрами (т. Е. C [x, y, z] = ...).

Я работал только с несколькими примерами динамического программирования и никогда не работал с одним, которому требуется 3 параметра при определении подзадачи. Я действительно потерялся здесь. Если кто-нибудь может осветить какой-то свет, который будет велик.

Моя догадка за то, что подзадача должна быть это:

С [х, у, г] = х число элементов из {a1, ... ау}, где сумма точно г

Но я понятия не имею, правильно ли это.

Answer 1

Один из способов разорвать этот на три параметров:

x: maximum index of item considered for inclusion in subset 
n: number of items in subset 
s: sum of subset 

Базовый случай C [0,0,0] = верно, C [0, я> 0, J> 0] = ложь

Рекурсивный случай:

C[i,n+1,s+a_i] = C[i-1,n,s] // use item i 
C[i,n,s] = C[i-1,n,s] // dont use item i 

При этом используется пространство O (N^2 * макс (a_i)) (может быть сведено к O (N * макс (a_i)) отбрасыванием C [I, ,] как используется)

Тогда просто найдите C [n, i, j] для j вблизи z для окончательного ответа.

В петле ...

for (int i = 1; i <= n; i++) 
{ 
    C[i,n+1,s+a_i] ||= C[i-1,n,s]; 
    C[i,n,s] ||= C[i-1,n,s]; 
} 

В рекурсивной функции:

bool C(int maxindex, int size, int sum) 
{ 
    if (memoize(maxindex, size, sum)) 
     return cached; 

    if (maxindex == 0) 
     return (size == 0 && sum == 0); 

    return 
     C(maxindex-1, size-1, sum - A[maxindex]) || // version using A[maxindex] 
     C(maxindex-1, size, sum); // version not using A[maxindex] 
} 

Answer 2

В этом случае я бы позволил C (x, y, z) быть булевым, представляющим, можно ли получить сумму точно z, используя ровно y из {a1 ... ax}.

Хотя это не та же самая проблема Wikipedia, имеет динамические программные решения для множества подобных проблем с объяснениями. Возможно, это может дать вам некоторые идеи.