0-1 Рюкзак пересмотрен

Question

Ну, это старая проблема с рюкзаком 0-1, но после нахождения полной максимальной цены я могу получить, мне нужно найти предметы, которые я могу носить. Но для следующего теста (всего 3 элементы)

10 (max weight that I can carry) 
5 3 (weight and value for each item) 
5 2 
6 5 

Здесь максимальная цена 5. Но для веса это может быть 6 или 10(5+5). Оба будут давать одинаковые цены, но, очевидно, целесообразно взять 6 кг товара, чем 10 кг. Я хочу намекнуть, как я могу вычислить это из матрицы dp. Я получил следующую матрицу для этого теста.

0 0 0 0 3 3 3 3 3 3 
0 0 0 0 3 3 3 3 3 5 
0 0 0 0 3 5 5 5 5 5 

Используя этот алгоритм, он находит вес 10, но оптимальный - 6 кг.

i=n, k=W(max weight)// n= total items 

while i,k > 0 

if dp[i,k] ≠ dp[i−1,k] then 
mark the ith item as in the knapsack 
i = i−1, k = k-w(weight of ith item) 

else 
i = i−1 

Answer 1

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

Это может быть сделано с помощью binary search на weigths [0,W] - так вы будете запускать алгоритм ранца всего O(logW) раз, давая вам всего O(nW*log(W)) решение, которое находит максимальное и минимальное значение возможного размера мешка.

Идея о том, как следует, бинарный поиск:
Пусть оригинальный мешок быть размером W, запустить knapsack(W,items) и получить value. Теперь проверьте, возвращается ли knapsack(W/2,items)value. Если это так - поиск в диапазоне (0,W/2]. Если это не так, выполните поиск в диапазоне (W/2,W], пока не найдете наименьший размер мешка, который возвращает value.