рекурсивный алгоритм ограниченного ранца

Question

Я борюсь с переводом рекурсивной задачи раннего динамического программирования 0-1 на динамический ограниченный рекурсивный рюкзак. Формула я в настоящее время используют в R является:

F(i,k)=max(v[i]+F(i-1, k-w[i]), F(i-1, k)) 

так что теперь я задаюсь вопросом, что эта функция стала бы для ограниченной динамической задачи о рюкзаке

спасибо

Answer 1

Самый простой модификации - сделать необходимо количество повторяющихся элементов

{3x1,2x5}=>{1,1,1,5,5} 

Другой подход - создать массив/вектор с числами копий и использовать его в рекурсивном c alls для проверки только записей с ненулевым количеством копий