Алгоритм ранца 0/1 - неограниченные ресурсы

Question

Я столкнулся с проблемой мышления, и я просто расстроен.У меня есть рабочий алгоритм задачи о ранце, использующий динамическое программирование, в котором я указываю

• Максимальная нагрузка
• Элементы (их вес)

иАлгоритм вычисляет оптимальное заполнение рюкзака, используя эти предметы.Но теперь мне нужно заполнить его полностью , используя минимум элементов, но у меня есть неограниченное количество каждого элемента.(Эти элементы имеют вес {1; w1; w2; ...}, поэтому их всегда можно выполнить).

Как мне вписать это в «классический» алгоритм?

Спасибо

Answer 1

Пусть

• M = Сумма, которую необходимо заполнить
• w [] = Массив весов
• dp [] = Массив оптимального заполнения (dp [i] содержит минимальное количество элементов, необходимое для заполнения веса i).

 initialize the dp array with INFINITY, dp[0] = 0;
 for(i = 0;i<size of w;i++) {
    for(j = 1;j<=M;j++) {
       if(j-w[i] >= 0) {
          dp[j] = min(dp[j], dp[j-w[i]]+1);
       }
    }
 }

 final solution is the value of dp[M];