Предмети

ВагаЦінність

Місткість

Місткість рюкзака: Пресети

Відтворення

Швидкість:

Показати жадібне порівняння

Статистика

Предметів—

Місткість—

Поточна клітинка—

Оптимальна цінність—

Обрані предмети—

Сумарна вага—

Жадібна цінність—

Заповнюємо dp[i][w] = max(dp[i-1][w], dp[i-1][w-wᵢ] + vᵢ) — пропустити предмет або взяти його. Коли таблиця заповнена, повертаємося від dp[n][W] назад, щоб відновити точний набір, який дає оптимум, і пакуємо його.