Блог

Главная - Вопросы по программированию - Формирование алгоритма динамического программирования для вариации задачи о рюкзаке

Формирование алгоритма динамического программирования для вариации задачи о рюкзаке

#algorithm #dynamic-programming #knapsack-problem

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

Вопрос:

Я думал,

Я хотел сделать вариацию проблемы с рюкзаком.

Представьте исходную проблему с элементами с различными весами / значениями.

Моя версия, наряду с обычными весами / значениями, будет содержать значение «group».

например. Элемент1 [5 кг, 600 долларов США, электронный] Элемент2 [1 кг, 50 долларов США, еда]

Теперь, имея набор таких элементов, как этот, как бы я закодировал проблему с рюкзаком, чтобы убедиться, что выбрано не более 1 элемента из каждой «группы».

Примечания:

  1. Вам не нужно выбирать элемент из этой группы
  2. В каждой группе есть несколько элементов
  3. Вы по-прежнему минимизируете вес, максимизируя ценность
  4. Количество групп предопределено вместе с их значениями.

На данном этапе я просто пишу черновик кода, и я решил использовать динамический подход. Я понимаю идею динамического решения обычной проблемы с рюкзаком, как мне изменить это решение, чтобы включить эти «группы»?

 KnapSackVariation(v,w,g,n,W)
{
  for (w = 0 to W)
     V[0,w] = 0;
  for(i = 1 to n)
     for(w = 0 to W)
        if(w[i] <= w)
           V[i,w] = max{V[i-1, w], v[i]   V[i-1, w-w[i]]};
        else
           V[i,w] = V[i-1, w];
     return V[n,W];
}

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

Комментарии:

1. Добавьте элемент группы в состояние!

2. Как насчет ее решения как задачи комбинаторной оптимизации? Для каждого элемента вы выбираете либо элемент, либо нет элемента. Возможно, вы захотите использовать поиск по ветвям и границам для ее решения.

Ответ №1:

просто заметил, что ваш вопрос пытается найти ответ на мой собственный вопрос. Проблема, которую вы изложили, является хорошо известной и хорошо изученной проблемой, называемой проблемой рюкзака с множественным выбором. Если вы погуглите, вы найдете всевозможную информацию, и я также могу порекомендовать эту книгу: http://www.amazon.co.uk/Knapsack-Problems-Hans-Kellerer/dp/3642073115/ref=sr_1_1?ie=UTF8amp;qid=1318767496amp;sr=8-1 , который посвящает этой проблеме целую главу. В классической формулировке MCKP вы должны выбрать один элемент из каждой группы. Однако вы можете легко преобразовать эту версию задачи в свою версию, добавив фиктивный элемент в каждую группу с profit и weight = 0, и будут работать те же алгоритмы. Я бы предостерег вас от попыток адаптировать код для двоичной задачи о рюкзаке к MCKP с помощью нескольких настроек — этот подход, вероятно, приведет вас к решению, производительность которого неприемлемо снижается по мере увеличения количества элементов в каждой группе.

Ответ №2:

Предположим
, что c [i]: категория i-го элемента
V [i, w, S]: максимальное значение рюкзака, такое, что он содержит максимум один элемент из каждой категории в S

 Recursive Formulation
V[i,w,S] = max(V[i-1,w,S],V[i,w-w[i],S-{c[i]}]   v[i])
Base Case
V[0,w,S] = -`infinity if w!=0 or S != {}`