Максимальная сумма значений N предметов в 0-1 ранце за счет уменьшения веса не более чем K предметов в два раза

Даны вес и стоимость N предметов и вместимость W рюкзака. Также учитывая, что вес не более чем K предметов может быть уменьшен до половины его первоначального веса. Задача состоит в том, чтобы найти максимальную сумму значений N предметов, которую можно получить так, чтобы сумма весов предметов в рюкзаке не превышала заданной вместимости W .

Примеры:

Input: W = 4, K = 1, value = [17, 20, 10, 15], weight = [4, 2, 7, 5]
Output: 37
Explanation: Change the weight of at most K items to half of the weight in a optimal way to get maximum value. Decrease the weight of first item to half and add second item weight the resultant sum of value is 37 which is maximum

Input: W = 8, K = 2, value = [17, 20, 10, 15], weight = [4, 2, 7, 5] 
Output: 53
Explanation: Change the weight of the last item and first item and the add the weight the of the 2nd item, The total sum value of item will be 53.

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

• Базовый случай: если индекс превышает длину значений, верните ноль.
• Если флаг равен K, максимум рассматривается 2 случая:
  • Включить товар с полным весом, если вес предмета не превышает остаточный вес
  • Пропустить элемент
• Если флаг меньше K, максимум рассматривается 3 случая:
  • Включить товар с полным весом, если вес предмета не превышает остаточный вес
  • Включить товар с половинным весом, если половинный вес предмета не превышает остаточный вес
  • Пропустить элемент

Временная сложность: O(3^N)
Вспомогательное пространство: O(N)