Formowanie algorytm programowania dynamicznego dla odmiany Knapsack problem

Question

więc myślałem,

chciałem zrobić odmianę plecaka problem.

Wyobraź sobie oryginalny problem z przedmiotami o różnych masach/wartościach.

Moja wersja wraz z normalnymi wartościami/wartościami zawiera "grupę".

np. Pozycja1 [5 kg, $ 600, Elektroniczny] ITEM2 [1 kg, $ 50, żywność]

Teraz, mając komplet przedmiotów, takich jak to, w jaki sposób mogę zakodować się problemu plecakowego, aby upewnić się, że maksymalnie 1 sztukę z każda "grupa" jest wybrana.

Uwagi:

1. Nie trzeba wybrać pozycję z tej grupy
2. Istnieje wiele elementów w każdej grupie
3. Ciągle minimalizuje wagę, wartość maksymalizacji
4. ilość predefiniowanych grup wraz z ich wartościami.

Właśnie piszę szkic kodu na tym etapie, a ja wybrałem dynamiczne podejście. Rozumiem ideę dynamicznego rozwiązania problemu zwykłego plecaka, jak mogę zmienić to rozwiązanie, aby włączyć te "grupy"?

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]; 
} 

To, co mam tak daleko, trzeba dodać go tak, że będzie usunąć wszystkie odpowiednie elementy z grupy to jest w każdej chwili rozwiązuje to.

Answer 1

Załóżmy
C [i]: rodzaj elementu ith
V [I, W, S] Maksymalna wartość plecaka, tak że zawiera on co max jednego elementu, z każdej kategorii w 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 != {}` 

Answer 2

właśnie zauważyłem twoje pytanie, próbując znaleźć odpowiedź na moje własne pytanie. Problem, o którym mówisz, jest dobrze znanym i dobrze zbadanym problemem o nazwie Problem z plecakiem wielokrotnego wyboru. Jeśli szukasz informacji w google, mogę również polecić tę książkę: http://www.amazon.co.uk/Knapsack-Problems-Hans-Kellerer/dp/3642073115/ref=sr_1_1?ie=UTF8&qid=1318767496&sr=8-1, która poświęca cały rozdział temu problemowi. W klasycznej formule MCKP musisz wybrać jeden przedmiot z każdej grupy. Możesz jednak łatwo przekonwertować tę wersję problemu do swojej wersji, dodając do każdej grupy obojętny przedmiot z zyskiem i wagą = 0, a te same algorytmy będą działać. Ostrzegałbym cię przed próbą adaptacji kodu dla problemu binarnego plecaka do MCKP za pomocą kilku poprawek - to podejście prawdopodobnie doprowadzi cię do rozwiązania, którego wydajność pogarsza się w sposób nieakceptowalny wraz ze wzrostem liczby pozycji w każdej grupie.