Завдання про рюкзак а що ж усередині
Високоповажний SergeyACTIVITI у своєму пості розповів нам про таку корисну річ, як завдання про рюкзак, рішення якого з успіхом реалізовано у вирішувачах COIN-OR або GLPK. А що ж усередині?
Отже, нехай у нас є рюкзак об'єму W, і список з n речей, кожна з яких має об'єм v[i] і вартість c[i], і кожну з яких можна брати скільки завгодно разів. При цьому всі обсяги та всі вартості будуть позитивними та цілими. Як працює алгоритм?
Заведемо масив max довжини W+1, в якому ми за підсумками роботи алгоритму отримаємо найбільшу вартість, яку може мати набір речей, що займає даний обсяг - для кожного об'єму від 0 до W включно. А точніше, після k ітерацій ми отримаємо для кожного об'єму i max[i] - максимальну можливу вартість набору речей об'єму i, в якому можуть бути лише перші k речей. Одразу зрозуміло, що спочатку треба ініціалізувати max[0] = 0. Що ж інші елементи max? Не використовуючи жодних речей, можна отримати лише набір ваги 0. Отже, в max[i] (0 = v[k]). Максимальну їх треба записати в max[i]. Отже, після k-тої ітерації ми отримаємо в кожному max[i] найбільшу вартість, яку може мати набір речей, складений із речей. Отже, після n ітерацій ми отримаємо саме те, що обіцялося. Залишилася справа техніки: пройтися масивом max[i] і вибрати в ньому максимальний елемент. Як неважко помітити, асимптотика часу роботи алгоритму буде O(W*n), і пам'яті, що використовується — O(W).
Варіації:1. Коли треба отримати не лише вартість, а й сам набір. Крім масиву max, запишемо ще й масив prev. У нього ми записуватимемо, яку річ ми востаннє поклали в набір. Тобто якщо при порівнянні max[i] і max[i-v[k]] + c[k] виявилося, щоmax[i-v[k]] + c[k] краще - це означає, що в оптимальному наборі ваги i повинен бути k-тий предмет. Таким чином, якщо ми з'ясували, що оптимальна вартість max[i] досягається при наборі ваги i, можна записати, що ми додали в набір річ prev[i]. І перейти до оптимального набору ваги i – v[prev[i]]. Там також подивитися, яку річ узяли востаннє. І так далі, поки не дійдемо до нуля.
2. Коли кожну річ можна брати лише один раз. Тут все ще простіше: треба просто в кожній ітерації йти масивом не знизу вгору, а зверху вниз, тобто, від W до 0. Тоді вийде, що при розгляді max [i-v [k]], там все ще буде записано, набір якої максимальної вартості ваги i - v[k] можна отримати, використовуючи лише речі 0..k-1. Отже, якщо вийде, що в оптимальному наборі треба використовувати k-ту річ, то вона буде використана лише один раз.
3. Вибір значення, якомога ближчого до даного.Якщо немає цін, цей алгоритм, очевидно, допомагає якомога сильніше набити рюкзак. Або ж, якщо йдеться не про рюкзак, і неважливо, що загальний обсяг речей не більше обсягу рюкзака, можна з кількох чисел за допомогою додавання отримати число, якомога ближче до даного.
У всіх випадках асимптотика часу роботи та пам'яті, що використовується, та ж.
4. Коли кожну річ можна брати певну кількість разів.За цю варіацію дякую lipstick. Є варіація задачі, у якій річ із номером i можна брати від 0 до q[i] разів. Звичайно, можна «розмножити» i-ю річ на q[i] одиниць і розв'язати задачу про 0-1 рюкзак. Однак складність такого рішення буде O(W * ∑q[i]), що не дуже добре. Насправді можна вчинити хитріше.
А у нас тут можна отримати грант на тестовий період Яндекс.Хмари. Варто лише вполе "секретний пароль" ввести "Хабр"