변종 배낭 프로그래밍에 대한 동적 프로그래밍 알고리즘

Question

그래서 저는 생각했습니다.

배낭 문제를 변형하고 싶었습니다.

다양한 가중치/값을 가진 항목과 함께 원래의 문제를 상상해보십시오.

내 버전은 일반적인 가중치/값과 함께 "그룹"값을 포함합니다.

예 : 항목 1 [5kg, $ 600 전자] 항목 2 내가 확인하기 위해 배낭 문제를 코드를 얼마나 이제 [1kg, $ 50 음식]

,이 같은 항목의 집합을 가지고, 그 한 항목의 최대에서 각 "그룹"이 선택됩니다.

주 :

1. 당신은 해당 그룹에서 항목을 선택할 필요가 없습니다
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]; 
} 

. i 번째 요소
V [I, W, S]의 종류 :

Answer 1

는
C [i]는 가정이 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

방금 ​​내 질문에 대한 답변을 찾으려고했습니다. 당신이 말한 문제는 Multiple Choice 배낭 문제라고하는 잘 알려져 있고 잘 연구 된 문제입니다. 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에 바이너리 배낭 문제에 대한 코드를 약간의 개조로 조정하는 것에 대해주의를 기울일 것입니다.이 접근법은 각 그룹의 항목 수가 증가함에 따라 성능이 부적절하게 떨어지는 솔루션으로 이끄는 가능성이 있습니다.