максимальная сумма подмножества размера K с суммой меньше M

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

Пусть dp[i][j][k] = true, если существует подмножество размера k первых i элементов входного массива, суммирующего до j

Наш базовый случай - dp[0][0][0] = true

Теперь либо размер k подмножества первых i элементов использует a[i + 1], либо нет, что дает повторение

dp[i + 1][j][k] = dp[i][j - a[i + 1]][k - 1] OR dp[i][j][k]

Сложите все вместе:

given A[1...N]
initialize dp[0...N][0...M][0...K] to false
dp[0][0][0] = true
for i = 0 to N - 1:
    for j = 0 to M:
        for k = 0 to K:
            if dp[i][j][k]:
                dp[i + 1][j][k] = true
            if j >= A[i] and k >= 1 and dp[i][j - A[i + 1]][k - 1]:
                dp[i + 1][j][k] = true
max_sum = 0
for j = 0 to M:
    if dp[N][j][K]:
        max_sum = j
return max_sum

придавая O(NMK) временную и пространственную сложность.

Возвращаясь назад, мы сделали одно предположение здесь неявно, а именно, что A[1...i] все неотрицательны. При отрицательных числах инициализация второго измерения 0...M неверна. Рассмотрим подмножество размера K, состоящее из подмножества размера K - 1 с суммой, превышающей M, и еще одного достаточно отрицательного элемента A[], так что общая сумма больше не превышает M. Точно так же наше подмножество размера K - 1 можно суммировать до некоторого крайне отрицательного числа, а затем с достаточно положительным элементом A[] суммировать до M. Чтобы наш алгоритм работал в обоих случаях, нам нужно увеличить второе измерение с M до разницы между суммой всех положительных элементов в A[] и суммой всех отрицательных элементов (сумма абсолютных значений всех элементов в A[]).

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

Сверх того? Что ж, ваша проблема тесно связана с суммой подмножества, и литература по широко известным неполным задачам NP довольно обширна. И, как общий принцип, алгоритмы могут быть всех форм и размеров - для меня вполне возможно представить себе, например, рандомизацию, аппроксимацию (просто выберите параметр ошибки достаточно малым!), Простое старое сокращение других полных проблем NP ( преобразуйте вашу проблему в гигантскую логическую схему и запустите решатель SAT). Да это разные алгоритмы. Они быстрее, чем решение для динамического программирования? Наверное, некоторые из них. Являются ли они такими же простыми для понимания или реализации, не говоря уже об обучении, помимо стандартного материала по введению в алгоритмы? Возможно нет.

Это вариант задачи о ранце или подмножестве, где с точки зрения времени (за счет экспоненциального роста требований к пространству по мере увеличения размера ввода) динамическое программирование является наиболее эффективным методом, который ПРАВИЛЬНО решает эту проблему. См. Этот вариант проще решить проблему с суммой подмножества? на вопрос, аналогичный вашему.

initialize dp[0..K][0..M] to false
dp[0][0] = true
for i = 0 to N:
    for s = 0 to K - 1:
        for j = M to 0:
            if dp[s][j] && A[i] + j < M:
                dp[s + 1][j + A[i]] = true
for j = M to 0:
    if dp[K][j]:
        print j
        break

Мы ищем подмножество K элементов, для которых сумма элементов максимальна, но меньше M.

Мы можем разместить границы [X, Y] на самом большом элементе в подмножестве следующим образом.

Сначала мы сортируем (N) целых чисел values[0] ... values[N-1], причем элемент values[0] является наименьшим.

Нижняя граница X - это наибольшее целое число, для которого

values[X] + values[X-1] + .... + values[X-(K-1)] < M.

(Если X равно N-1, значит, мы нашли ответ.)

Верхняя граница Y - это наибольшее целое число меньше N, для которого

values[0] + values[1] + ... + values[K-2] + values[Y] < M.

С помощью этого наблюдения мы можем теперь связать второй по величине член для каждого значения самого высокого члена Z, где

X <= Z <= Y.

Мы можем использовать точно такой же метод, поскольку форма задачи точно такая же. Уменьшенная проблема заключается в поиске подмножества K-1 элементов, взятых из values[0] ... values[Z-1], для которого сумма элементов является максимальной, но меньше M - values[Z].

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

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

Феликс прав, что это частный случай задачи о рюкзаке. Его алгоритм динамического программирования занимает O (K * M) размер и O (K * K * M) количество времени. Я считаю, что его использование переменной N действительно должно быть K.

Задаче о рюкзаке посвящены две книги. Последний, Келлерер, Пферши и Писингер [2004, Springer-Verlag, ISBN 3-540-40286-1], дает улучшенный алгоритм динамического программирования на своей странице 76, рисунок 4.2, который занимает O ( K + M) пространство и O (KM) время, что является огромным сокращением по сравнению с алгоритмом динамического программирования, данным Феликсом. Обратите внимание на опечатку в последней строке алгоритма книги, где должно быть c-bar: = c-bar - w_ (r (c-bar)).

Моя реализация на C # ниже. Я не могу сказать, что я тщательно его тестировал, и я приветствую отзывы по этому поводу. Я использовал BitArray для реализации концепции наборов, представленных в алгоритме в книге. В моем коде c - это емкость (которая в исходном посте называлась M), и я использовал w вместо A в качестве массива, содержащего веса.

Пример его использования:

int[] optimal_indexes_for_ssp = new SubsetSumProblem(12, new List<int> { 1, 3, 5, 6 }).SolveSubsetSumProblem();

где массив optimal_indexes_for_ssp содержит [0,2,3], соответствующие элементам 1, 5, 6.

using System;
using System.Collections.Generic;
using System.Collections;
using System.Linq;

public class SubsetSumProblem
{
    private int[] w;
    private int c;

    public SubsetSumProblem(int c, IEnumerable<int> w)
    {
      if (c < 0) throw new ArgumentOutOfRangeException("Capacity for subset sum problem must be at least 0, but input was: " + c.ToString());
      int n = w.Count();
      this.w = new int[n];
      this.c = c;
      IEnumerator<int> pwi = w.GetEnumerator();
      pwi.MoveNext();
      for (int i = 0; i < n; i++, pwi.MoveNext())
        this.w[i] = pwi.Current;
    }

    public int[] SolveSubsetSumProblem()
    {
      int n = w.Length;
      int[] r = new int[c+1];
      BitArray R = new BitArray(c+1);
      R[0] = true;
      BitArray Rp = new BitArray(c+1);
      for (int d =0; d<=c ; d++) r[d] = 0;
      for (int j = 0; j < n; j++)
      {
        Rp.SetAll(false);
        for (int k = 0; k <= c; k++)
          if (R[k] && k + w[j] <= c) Rp[k + w[j]] = true;
        for (int k = w[j]; k <= c; k++) // since Rp[k]=false for k<w[j]
          if (Rp[k])
          {
            if (!R[k]) r[k] = j;
            R[k] = true;
          }
      }
      int capacity_used= 0;
      for(int d=c; d>=0; d--)
        if (R[d])
        {
          capacity_used = d;
          break;
        }
      List<int> result = new List<int>();
      while (capacity_used > 0)
      {
        result.Add(r[capacity_used]);
        capacity_used -= w[r[capacity_used]];
      } ;
      if (capacity_used < 0) throw new Exception("Subset sum program has an internal logic error");
      return result.ToArray();
    }
}