Видимо, с выражением мыслей у меня совсем плохо иногда.
Ну, не, вы совершенно верно сказали:
все элементы распределяются по всем рюкзакам модификацией алгоритма с одним рюкзаком, чтобы числа вхождений 0 и 1 переинтерпретировались как рюкзак, в который мы распределили элемент
Даже поиск в глубину имеет некоторый порядок перебора (интересно, делает ли этот факт предыдущий алгоритм тоже поиском в глубину). И в практической реализации алгоритма, действительно появляется массив, где для каждого элемента исходного множества записан номер суммы, в которую этот элемент отправляется.
Я не согласился (и был прав), в том, что порядок перебора в текущем алгоритме не имеет ничего нового с порядком перебора в старом (однорюкзачном). И механизм отсечений планируется тоже совершенно иной (хотя одно из отсечений, где сумму нельзя уменьшить ниже нуля, — очень похожее отсечение). Я уже реализовал простейший алгоритм. В нём порядок перебора получился самый обыденный: позиционная запись с последовательным инкрементом индексов сумм и переносами в следующий разряд, если все суммы в текущем перебраны. Алгоритм сейчас чуть-чуть лучше лобового брутфорса с перебором
вариантов (где
— число сумм, а
— число элементов, из которых их надо составить) за счёт того, что как раз производится отсечение ситуаций, где из остатка суммы запрещается вычитать слагаемое, большее остатка.
Ключевое отсечение пока не реализовывал. Но результаты кое-какие уже есть:
(ПРИМЕР РАЗ)
Values = [2, 10, 10, 11, 16, 16, 18, 21]
Taget sums = [39, 32, 33]
RESULT = [2, 2, 2, 2, 1, 1, 0, 0]
RESULT = [2, 2, 0, 0, 1, 1, 0, 2]
RESULT = [2, 0, 2, 0, 1, 1, 0, 2]
(ПРИМЕР ДВА)
Values = [1, 2, 3, 3, 3]
Taget sums = [6, 6]
RESULT = [1, 1, 1, 0, 0]
RESULT = [1, 1, 0, 1, 0]
RESULT = [0, 0, 1, 1, 0]
RESULT = [1, 1, 0, 0, 1]
RESULT = [0, 0, 1, 0, 1]
RESULT = [0, 0, 0, 1, 1]
(ПРИМЕР ТРИ)
Values = [4, 4, 6, 6, 6, 6, 7, 7, 7]
Taget sums = [16, 20, 17]
RESULT = [2, 0, 2, 1, 0, 0, 2, 1, 1]
RESULT = [0, 2, 2, 1, 0, 0, 2, 1, 1]
RESULT = [2, 0, 1, 2, 0, 0, 2, 1, 1]
RESULT = [0, 2, 1, 2, 0, 0, 2, 1, 1]
RESULT = [2, 0, 2, 0, 1, 0, 2, 1, 1]
RESULT = [0, 2, 2, 0, 1, 0, 2, 1, 1]
RESULT = [2, 0, 0, 2, 1, 0, 2, 1, 1]
RESULT = [0, 2, 0, 2, 1, 0, 2, 1, 1]
RESULT = [2, 0, 1, 0, 2, 0, 2, 1, 1]
RESULT = [0, 2, 1, 0, 2, 0, 2, 1, 1]
RESULT = [2, 0, 0, 1, 2, 0, 2, 1, 1]
RESULT = [0, 2, 0, 1, 2, 0, 2, 1, 1]
RESULT = [2, 0, 2, 0, 0, 1, 2, 1, 1]
RESULT = [0, 2, 2, 0, 0, 1, 2, 1, 1]
RESULT = [2, 0, 0, 2, 0, 1, 2, 1, 1]
RESULT = [0, 2, 0, 2, 0, 1, 2, 1, 1]
RESULT = [2, 0, 0, 0, 2, 1, 2, 1, 1]
RESULT = [0, 2, 0, 0, 2, 1, 2, 1, 1]
RESULT = [2, 0, 1, 0, 0, 2, 2, 1, 1]
RESULT = [0, 2, 1, 0, 0, 2, 2, 1, 1]
RESULT = [2, 0, 0, 1, 0, 2, 2, 1, 1]
RESULT = [0, 2, 0, 1, 0, 2, 2, 1, 1]
RESULT = [2, 0, 0, 0, 1, 2, 2, 1, 1]
RESULT = [0, 2, 0, 0, 1, 2, 2, 1, 1]
RESULT = [2, 0, 2, 1, 0, 0, 1, 2, 1]
RESULT = [0, 2, 2, 1, 0, 0, 1, 2, 1]
RESULT = [2, 0, 1, 2, 0, 0, 1, 2, 1]
RESULT = [0, 2, 1, 2, 0, 0, 1, 2, 1]
RESULT = [2, 0, 2, 0, 1, 0, 1, 2, 1]
RESULT = [0, 2, 2, 0, 1, 0, 1, 2, 1]
RESULT = [2, 0, 0, 2, 1, 0, 1, 2, 1]
RESULT = [0, 2, 0, 2, 1, 0, 1, 2, 1]
RESULT = [2, 0, 1, 0, 2, 0, 1, 2, 1]
RESULT = [0, 2, 1, 0, 2, 0, 1, 2, 1]
RESULT = [2, 0, 0, 1, 2, 0, 1, 2, 1]
RESULT = [0, 2, 0, 1, 2, 0, 1, 2, 1]
RESULT = [2, 0, 2, 0, 0, 1, 1, 2, 1]
RESULT = [0, 2, 2, 0, 0, 1, 1, 2, 1]
RESULT = [2, 0, 0, 2, 0, 1, 1, 2, 1]
RESULT = [0, 2, 0, 2, 0, 1, 1, 2, 1]
RESULT = [2, 0, 0, 0, 2, 1, 1, 2, 1]
RESULT = [0, 2, 0, 0, 2, 1, 1, 2, 1]
RESULT = [2, 0, 1, 0, 0, 2, 1, 2, 1]
RESULT = [0, 2, 1, 0, 0, 2, 1, 2, 1]
RESULT = [2, 0, 0, 1, 0, 2, 1, 2, 1]
RESULT = [0, 2, 0, 1, 0, 2, 1, 2, 1]
RESULT = [2, 0, 0, 0, 1, 2, 1, 2, 1]
RESULT = [0, 2, 0, 0, 1, 2, 1, 2, 1]
RESULT = [2, 0, 2, 1, 0, 0, 1, 1, 2]
RESULT = [0, 2, 2, 1, 0, 0, 1, 1, 2]
RESULT = [2, 0, 1, 2, 0, 0, 1, 1, 2]
RESULT = [0, 2, 1, 2, 0, 0, 1, 1, 2]
RESULT = [2, 0, 2, 0, 1, 0, 1, 1, 2]
RESULT = [0, 2, 2, 0, 1, 0, 1, 1, 2]
RESULT = [2, 0, 0, 2, 1, 0, 1, 1, 2]
RESULT = [0, 2, 0, 2, 1, 0, 1, 1, 2]
RESULT = [2, 0, 1, 0, 2, 0, 1, 1, 2]
RESULT = [0, 2, 1, 0, 2, 0, 1, 1, 2]
RESULT = [2, 0, 0, 1, 2, 0, 1, 1, 2]
RESULT = [0, 2, 0, 1, 2, 0, 1, 1, 2]
RESULT = [2, 0, 2, 0, 0, 1, 1, 1, 2]
RESULT = [0, 2, 2, 0, 0, 1, 1, 1, 2]
RESULT = [2, 0, 0, 2, 0, 1, 1, 1, 2]
RESULT = [0, 2, 0, 2, 0, 1, 1, 1, 2]
RESULT = [2, 0, 0, 0, 2, 1, 1, 1, 2]
RESULT = [0, 2, 0, 0, 2, 1, 1, 1, 2]
RESULT = [2, 0, 1, 0, 0, 2, 1, 1, 2]
RESULT = [0, 2, 1, 0, 0, 2, 1, 1, 2]
RESULT = [2, 0, 0, 1, 0, 2, 1, 1, 2]
RESULT = [0, 2, 0, 1, 0, 2, 1, 1, 2]
RESULT = [2, 0, 0, 0, 1, 2, 1, 1, 2]
RESULT = [0, 2, 0, 0, 1, 2, 1, 1, 2]
Ищутся все возможные представления. Но из-за повторяющихся элементов есть повторы решений. Это, в частности, замедляет поиск, поскольку приходится перебирать комбинации, которые уже были перебраны. Вот, думаю: как бы это исправить?
Код на данный момент такой:
import java.util.*;
public class StudyKnapsackProblem {
private static int[] values = new int[]
// {4, 4, 6, 6, 6, 6, 7, 7, 7};
// {2, 10, 10, 11, 16, 16, 18, 21};
// {6, 6, 6, 13, 13, 22, 22, 22, 22, 46, 46, 48, 48};
// {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
{1, 2, 3, 3, 3};
private static int[] tagetSums = new int[]
// {16, 20, 17};
// {39, 32, 33};
// {74, 81, 89, 76};
// {12, 13, 14, 16};
{6, 6};
public static void main(String[] args) {
int valuesNumber, sumsNumber, index, value, sum, sumIndex;
int[] sumIndices, sums;
boolean isDebug;
System.out.print("Values = ");
System.out.println(Arrays.toString(values));
System.out.print("Taget sums = ");
System.out.println(Arrays.toString(tagetSums));
System.out.println();
valuesNumber = values.length;
sumsNumber = tagetSums.length;
sumIndices = new int[valuesNumber];
sums = Arrays.copyOf(tagetSums, sumsNumber);
index = valuesNumber - 1;
isDebug = false;
while (true) {
sumIndex = sumIndices[index];
if (isDebug) {
System.out.print("index = ");
System.out.println(index);
System.out.print("sums = ");
System.out.println(Arrays.toString(sums));
System.out.print("sumIndex = ");
System.out.println(sumIndex);
}
if (sumsNumber == sumIndex) {
++index;
if (valuesNumber == index) {
break;
}
sumIndex = sumIndices[index];
sums[sumIndex] += values[index];
++sumIndex;
sumIndices[index] = sumIndex;
} else {
value = values[index];
sum = sums[sumIndex];
if (isDebug) {
System.out.print("value = ");
System.out.println(value);
System.out.print("sumIndices = [");
display(sumIndices, index);
System.out.println("]");
}
if (sum >= value) {
sums[sumIndex] = sum - value;
if (0 != index) {
--index;
sumIndices[index] = 0;
} else {
if (isDebug) {
System.out.println();
}
System.out.print("RESULT = ");
System.out.println(Arrays.toString(sumIndices));
sums[sumIndex] += value;
++sumIndex;
sumIndices[index] = sumIndex;
}
} else {
++sumIndex;
sumIndices[index] = sumIndex;
}
}
if (isDebug) {
System.out.println();
}
}
}
private static void display(int[] data, int index) {
int n, size;
size = data.length;
for (n = 0; size > n; ++n) {
if (0 != n) {
System.out.print(", ");
}
if (index >= n) {
System.out.print("?");
} else {
System.out.print(data[n]);
}
}
}
}
повторяющимся элементам соответствует мультимножество мощности 
корзинам. Есть подозрение, что это должно быть что-то вроде биномиального коэффициента, но для моего примера выше, где 
и 
, этот коэффициент равен 10, а в вашем примере (с 
и 
) — 35. 
или 
что ли? Откуда он такой берётся и почему он меньше, чем 
?
. 
Не понятно, как получается, что 
(причём равенство достигается при 
или 
). Ну да ладно, всё равно я тут подумал: количество итераций слабо перекликается с потенциальным числом перебираемых комбинаций, так как на сборку целой комбинации уходит несколько итераций, плюс не все комбинации собираются до конца, плюс не все начинают собираться с нуля как в случае брутфорса в лоб и плюс ещё нужны итерации для деконструкции комбинации (даже если она не собрана полностью).