GeeksforGeeks

Ми використовуємо файли cookie, щоб забезпечити найкращий досвід перегляду веб-сайту. Використовуючи наш веб-сайт, ви підтверджуєте, що прочитали та розумієте нашу Політику використання файлів cookie та Політику конфіденційності

Вам дають мішок розміром W кг, і ви отримуєте вартість пакетів з різною вагою апельсинів вартістю масиву [], де вартість [i] - це в основному вартість «Я» кг пачки апельсинів. Де вартість [i] = -1 означає це «Я» кг упаковки апельсина недоступний
Знайдіть мінімальну загальну вартість, щоб придбати апельсини рівно W кг, а якщо неможливо придбати апельсини точно W кг, то надрукуйте -1. Можна припустити, що існує безмежна кількість усіх доступних типів пакетів.
Примітка: масив починається з індексу 1.

Приклади:

Цю проблему можна звести до необмеженого рюкзака. Отже, у масиві витрат ми спочатку ігноруємо ті пакети, які недоступні, тобто; вартість дорівнює -1, а потім пройдіть масив витрат і створіть два масиви val [] для зберігання вартості «Я» кг пачки апельсина та мас. [] для зберігання ваги відповідної пачки. Припустимо, що вартість [i] = 50, тому вага пакета буде дорівнювати i, а вартість складе 50.
Алгоритм:

Створіть матрицю min_cost [n + 1] [W + 1], де n - кількість різних зважених пакетів оранжевого кольору, а W - максимальна місткість пакета.
Ініціалізуємо 0-й рядок INF (нескінченність) і 0-й стовпець 0.
Тепер заповніть матрицю
- якщо wt [i-1]> j, тоді min_cost [i] [j] = min_cost [i-1] [j];
- якщо wt [i-1] filter_none