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

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

6 голосов
/ 07 октября 2011

Я думал,

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

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

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

например. Item1 [5 кг, $ 600, электронное] Item2 [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];
}

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

Ответы [ 2 ]

3 голосов
/ 16 октября 2011

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

0 голосов
/ 09 октября 2011

Предположим,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 != {}`
...