Неограниченный ранец (повторение предметов разрешено) | Набор 2

Даны целое число W , массивы val[] и wt[] , где val[i] и wt[i] — значения и веса i ^-го элемента, задача состоит в том, чтобы вычислить максимальное значение, которое можно получить, используя веса, не превышает В.
Примечание. Каждый вес может быть указан несколько раз.

Примеры:

Input: W = 4, val[] = {6, 18}, wt[] = {2, 3}
Output: 18
Explaination: The maximum value that can be obtained is 18, by selecting the 2^nd item twice.

Input: W = 50, val[] = {6, 18}, wt[] = {2, 3}
Output: 294

Наивный подход: обратитесь к предыдущему сообщению, чтобы решить проблему с использованием традиционного алгоритма Unbounded Knapsack.
Временная сложность: O(N * W)
Вспомогательное пространство: O(W)

Эффективный подход. Описанный выше подход можно оптимизировать на основе следующих наблюдений:

• Предположим, i ^-й индекс дает нам максимальное значение на единицу веса в заданных данных, которое можно легко найти за O(n) .
• Для любого веса X , большего или равного wt[i] , максимально достижимое значение будет dp[X – wt[i]] + val[i] .
• Мы можем вычислить значения dp[] от 0 до wt[i] , используя традиционный алгоритм, и мы также можем рассчитать количество экземпляров i ^-го элемента, которые мы можем поместить в вес W.
• Таким образом, требуемый ответ будет val[i] * (W/wt[i]) + dp[W%wt[i]] .
  

Ниже представлена реализация нового алгоритма.

Временная сложность : O(N + min(wt[i], W) * N)
Вспомогательное пространство: O(W)