Проблема сумм подмножеств, разрыв связей по начальному порядку

Question

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

Например, для массива [2, 5, 1, 3, 4, 5] и N = 6 результат должен быть {2, 1, 3}. Хотя {5, 1}, {2, 4} и {1, 5} также являются подмножествами, общая сумма которых составляет до 6, нам нужно вернуть {2, 1, 3} в соответствии с порядком чисел в массиве.

Для классической задачи я знаю, как это сделать с динамическим программированием, но чтобы разорвать связи, я не могу придумать лучшего подхода, кроме как сначала найти ВСЕ возможные подмножества, а затем выбрать тот, который имеет наилучший порядок. Есть идеи?

Answer 1

Я постараюсь представить интересный способ разрыва связей. Давайте назначим другое значение элементам, пусть значение элемента i_th будет называться v [i] .

Пусть есть T элементовэлемент i-й будет иметьзнак равно, вес =.

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

Вот практический пример:

Рассмотрим N = 8, как предельный вес, который у нас есть.

Элементы {8, 4, 2, 2}

Значения {8, 4, 2, 1}

У нас будет два различных подмножества с весовой суммой = 8, {8} и {4, 2, 2}. Но первое имеет накопленное значение = 8, а другое - накопленное_значение = 7, поэтому мы выберем {8} вместо {4, 2, 2}.

Идея состоит в том, чтобы сформулировать динамическое программирование, котороеучитывает общую стоимость.

= максимальное накопленное значение среди всех подмножеств элементов из интервала [0, i], которые имеют общий вес = W.

Я дам псевдокод для решения

Set all DP[i][j] = -infinity

DP[0][0] = 0

for(int weight = 0; weight <= N; ++weight ) 
{
    for(int item = 0; item < T; ++item ) 
    {
        DP[item][weight] = DP[item - 1][weight]; // not using the current item
        if( v[item] < weight ) continue;
        else 
        {
            DP[item][weight] = max( DP[item][weight], DP[item - 1][ weight - w[item]] + v[item])
        }
    }
}

Каквосстановить элементы действительно тривиально после запуска алгоритма. DP [T] [N] будет суммой степеней двух (или -infinity, если невозможно выбрать элементы с суммой до N), а элемент i-й принадлежит ответу, еслии только если (DP [T] [N] & v [i]) == v [i].