Сумма динамического программирования

Обычная формулировка для этого состоит в том, что вы ищете значение, наиболее близкое к K., но не превышающее его. Если вы имеете в виду «меньше K», это просто означает, что ваше значение K на единицу больше обычного. Если вы действительно имеете в виду просто «не равно K», то вы в основном прогоните алгоритм дважды, сначала найдя наибольшую сумму меньше K, затем снова найдя наименьшую сумму больше K, а затем выбрав ту из тех, абсолютная сумма которых отличие от К наименьшее.

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

Основная идея довольно проста, хотя (по крайней мере, потенциально) использует много места для хранения. Мы строим таблицу с K + 1 столбцом и N + 1 строкой (где N = количество входов). Мы инициализируем первую строку таблицы нулями.

Затем мы начинаем проходить по таблице и строить наилучшее возможное значение для каждого возможного максимального значения вплоть до реального максимума, идя строка за строкой, поэтому мы начинаем только с одного входа, затем с двух возможных входов, затем с тремя и т. Д. . В каждой точке таблицы есть только две возможности для наилучшего значения: предыдущее наилучшее значение, которое не использует текущий ввод, или же текущий ввод плюс предыдущее наилучшее значение для максимума минус текущий ввод (и поскольку мы вычисляем значения таблицы по порядку, у нас всегда уже будет это значение).

Мы также обычно хотим отслеживать, какие элементы фактически использовались для получения результата. Для этого мы устанавливаем логическое значение для данного места в таблице в значение true тогда и только тогда, когда мы вычисляем значение для этого места в таблице, используя новый ввод для этой строки (а не просто копируя лучшее значение предыдущей строки). Наилучший результат находится в правом нижнем углу, поэтому мы начинаем с него и идем назад по таблице по одной строке за раз. Когда мы переходим к строке, в которой для логического значения этого столбца установлено значение true, мы знаем, что нашли ввод, который был использован. Мы распечатываем этот элемент, а затем вычитаем его из общей суммы, чтобы получить следующий столбец слева, где мы найдем следующий ввод, который использовался для создания этого вывода.

Вот реализация, технически написанная на C ++, но написанная в основном в стиле C, чтобы сделать каждый шаг как можно более явным.

#include <iostream>
#include <functional>

#define elements(array) (sizeof(array)/sizeof(array[0]))

int main() {

    // Since we're assuming subscripts from 1..N, I've inserted a dummy value
    // for v[0].
    int v[] = {0, 7, 15, 2, 1};

    // For the moment I'm assuming a maximum <= MAX.
    const int MAX = 17;

    // ... but if you want to specify K as the question implies, where sum<K, 
    // you can get rid of MAX and just specify K directly:
    const int K = MAX + 1;

    const int rows = elements(v);

    int table[rows][K] = {0};
    bool used[rows][K] = {false};

    for (int i=1; i<rows; i++)
        for (int c = 0; c<K; c++) {
            int prev_val = table[i-1][c];
            int new_val;

            // we compute new_val inside the if statement so we won't 
            // accidentally try to use a negative column from the table if v[i]>c
            if (v[i] <= c && (new_val=v[i]+table[i-1][c-v[i]]) > prev_val) {
                table[i][c] = new_val;
                used[i][c] = true;
            }
            else
                table[i][c] = prev_val;
        }

    std::cout << "Result: " << table[rows-1][MAX] << "\n";
    std::cout << "Used items where:\n";
    int column = MAX;
    for (int i=rows; i>-1; i--)
        if (used[i][column]) {
            std::cout << "\tv[" << i << "] = " << v[i] << "\n";
            column -= v[i];
        }

    return 0;
}

Есть пара вещей, которые вы обычно оптимизируете в этом (я этого не делал для удобства чтения). Во-первых, если вы достигнете оптимальной суммы, вы можете прекратить поиск, поэтому в этом случае мы могли бы фактически выйти из цикла, прежде чем вообще рассматривать окончательный ввод 1 (поскольку 15 и 2 дают желаемый результат 17).

Во-вторых, в самой таблице мы действительно используем только две строки в любой момент времени: одну текущую строку и одну предыдущую. Строки до этого (в основной таблице) больше никогда не используются (т. Е. Для вычисления строки [n] нам нужны значения из row[n-1], но не из row[n-2], row[n-3], ... row[0]. Чтобы уменьшить объем хранилища, мы можем сделать основной table состоит только из двух строк, и мы меняем местами между первой и второй строками. Очень похожий на C трюк для этого будет заключаться в использовании только младшего значащего бита номера строки, поэтому вам нужно заменить table[i] и table[i-1] на table[i&1] и table[(i-1)&1] соответственно (но только для основной таблицы - не при обращении к used таблице.

Вот пример на Python:

def closestSum(a,k):
  s={0:[]}
  for x in a:
    ns=dict(s)
    for j in s:
      ns[j+x]=s[j]+[x]
    s=ns
  if k in s:
    del s[k]
  return s[min(s,key=lambda i:abs(i-k))]

Пример:

>>> print closestSum([1,2,5,6],10)
[1, 2, 6]

Идея состоит в том, чтобы просто отслеживать, какие суммы могут быть получены из всех предыдущих элементов, когда вы просматриваете массив, а также один способ получить эту сумму. В конце вы просто выбираете самое близкое к тому, что хотите. Это решение динамического программирования, потому что оно разбивает общую проблему на подзадачи и использует таблицу для запоминания результатов подзадач вместо их пересчета.

Идея Катона в Racket:

#lang racket
(define (closest-sum xs k)
  (define h (make-hash '([0 . ()])))
  (for* ([x xs] [(s ys) (hash-copy h)])
    (hash-set! h (+ x s) (cons x ys))
    (hash-set! h x (list x)))
  (when (hash-ref h k #f) (hash-remove! h k))
  (cdr (argmin (λ (a) (abs (- k (car a)))) (hash->list h))))

Чтобы получить еще более лаконичную программу, можно взять лаконичный -hash.rkt с GitHub и напишите:

(define (closest-sum xs k)
  (define h {make '([0 . ()])})
  (for* ([x xs] [(s ys) {copy h}])
    {! h (+ x s) (cons x ys)}
    {! h x (list x)})
  (when {h k #f} {remove! h k})
  (cdr (argmin (λ (a) (abs (- k (car a)))) {->list h})))