Динамическое программирование с наборами

Question

У меня типичный вопрос в динамическом программировании.

Мой вопрос задан для массива = {1,2,3,4,5,6}, я должен найти все массивы, сумма которых является самой большой k. Если я рассмотрю все множества, он станет экспоненциальным alogorthm. Я думал об этом благодаря Dynamic Programming.

Suppose f k =7, 
My idea is 
Pass 1: {1],{2}....{6} 
Pass 2: Pass1 + {1,2},{1,3},{1,4},{1,5} 
Pass 3: Pass2 + {1,2,3}, 

И мое слово останавливается.

Im не в состоянии сформулировать это с помощью динамического программирования. Любые входы? Как сформулировать этот алгоритм в программу?

Answer 1

Ваша проблема - это пример knapsack problem, чья проблема с решением проблемы, как известно, является NP-полной. это означает, что, безусловно, не будет субэкспоненциального алгоритма (хотя математическое доказательство отсутствует).

Комментарий ZachLangleys показывает, что перечисление всех решений будет по-прежнему экспоненциальным в худшем случае, даже если бы был эффективный решатель задач, так как для получения результата уже требуется экспоненциальное время.

Поскольку проблема решения NP-полная, подсчет не может быть проще (иначе вы бы посчитали и затем проверили результат, равный 0 или нет).

Answer 2

решение

DP-за проблемы должны следовать следующей рекурсивную формулу, и строить снизу вверх:

f(i,0) = {{}} //a set containing only an empty set 
f(0,W) = {{}} (W > 0) 
f(0,W) = {} (W < 0) //an empty set 
f(i,W) = f(i-1,W) [union] extend(f(i-1,w-element[i]),element[i]) 

где функция расширения (набор, е):

extend(set,e): 
    for each s in set: //s is a set itself 
     s.add(e) 

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