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

Question

Дано: массив целых чисел K,M

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

Есть ли решение для не динамического программирования для этой проблемы? или если это только dp[i][j][k] может решить только этот тип проблемы! не могли бы вы объяснить алгоритм.

Answer 1

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

Однако, поскольку ваша проблема не совсем та же, я все равно предоставлю объяснение. Позволять dp[i][j] знак равно trueесли есть подмножество длины i это сумма j а также false если нет Идея в том, что dp[][] будет кодировать суммы всех возможных подмножеств для каждой возможной длины. Затем мы можем просто найти самый большой j <= M такой, что dp[K][j] является true, Наш базовый случай dp[0][0] = true потому что мы всегда можем сделать подмножество с суммой 0, выбрав одно из размера 0.

Рецидив также довольно прост. Предположим, мы рассчитали значения dp[][] используя первый n значения массива. Чтобы найти все возможные подмножества первого n+1 Значения массива, мы можем просто взять n+1_th value и добавьте его ко всем подмножествам, которые мы видели ранее. Более конкретно, у нас есть следующий код:

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

Answer 2

Мы ищем подмножество 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.

Answer 3

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

Есть две книги, посвященные проблеме рюкзака. Последний из них, Kellerer, Pferschy and Pisinger [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 это емкость (которая в оригинальном посте называлась М), и я использовал 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();
    }
}