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

#algorithm #dynamic-programming #knapsack-problem

#алгоритм #динамическое программирование #ранец-проблема

Вопрос:

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

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

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

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

Спасибо

1. эта проблема эквивалентна проблеме размена монет people.csail.mit.edu/bdean/6.046/dp перейдите по ссылке, чтобы узнать больше о проблемах динамического программирования

2. Это действительно похоже на это, да. Но ссылки на странице, которую вы предоставили, открывают только пустое окно:/ Все равно спасибо

3. Неважно, я сам ввел адрес, на который указывает команда JS. Его можно найти по адресу people.csail.mit.edu/bdean/6.046/dp/dp_2.swf

Ответ №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];