Я знаю, как решить проблему с рюкзаком 0-1 с помощью подхода динамического программирования, но у меня возникают проблемы с выяснением того, какие предметы брать, не ставя под угрозу сложность O (N * C) (N предметов, C вместимость).
Любые идеи (я бы предпочел подход снизу вверх)?
Предположим, прямо сейчас вы сохраняете результаты в массиве bool[] a, где a[i] истинно, когда сумма i может быть достигнута.
Вам понадобится еще один массив int[] b, где b[i] — это последний элемент, который вы поместили в рюкзак для достижения суммы i.
Итак, где у вас было
a[i] = true;
тебе понадобиться
a[i] = true;
b[i] = current_item;
Затем поиск предметов, которые можно взять для достижения суммы i, представляет собой простой цикл.
PS Я использую два массива для простоты, но очевидно, что массив a можно убрать.
O(N * C), но использует пространство O(N * C). Я не думаю, что реконструкция возможна только с одним или двумя массивами.
- person eold; 16.02.2011
b или использовании ее для воссоздания решения?
- person Nikita Rybak; 06.07.2011
b для воссоздания решения?
- person axel22; 06.07.2011
function recreate(i) {return b[i] + recreate(i - cost[b[i]])}
- person Nikita Rybak; 06.07.2011
Вот модификация для восстановления пути в O (n) раз
int knapsack(int weight[], int profit[], int no_of_items, int capacity) {
for (int var = 0; var <= capacity; ++var) {
dp[0][var] = 0;
}
for (int var = 0; var <= no_of_items; ++var) {
path[var] = false;
}
int using_item_i, without_using_item_i;
for (int i = 1; i <= no_of_items; ++i) {
for (int j = 1; j <= capacity; ++j) {
without_using_item_i = dp[i - 1][j];
using_item_i = 0;
if ((weight[i]) <= j) {
using_item_i = dp[i - 1][j - weight[i]] + profit[i];
}
if (using_item_i >= without_using_item_i) {
taken[i][j] = true;
dp[i][j] = using_item_i;
} else {
taken[i][j] = false;
dp[i][j] = without_using_item_i;
}
}
}
//Reconstructing back the path
int j = capacity;
for (int i = no_of_items; i >= 0; --i) {
if (taken[i][j]) {
path[i] = true;
cnt++;
}
j = j - weight[i];
}
return dp[no_of_items][capacity];
}
Проверьте соль на прикрепленном изображении
https://www.dropbox.com/s/ish7t5vgy91fovt/Screenshot%202017-01-01%2015.16.31.png?dl=0
Распечатайте tmpList в вызывающем, и вы получите ответ
