Spoj 배낭 DP explaination

Question

spoj.I에서 문제를 해결하기 위해 노력하고 있는데, 나는 dp 솔루션을 만들었지 만 잘못된 대답을 제공합니다. 나는 dp 매트릭스를 생성하고 이전의 대답과 현재의 응답을 최대로 취하고 있습니다.

누구나 문제의 적절한 해결책을 설명 할 수 있습니까? https://www.spoj.pl/problems/BACKPACK/

Answer 1

방금이 문제가 발생했습니다.

"dp solution"이 정확히 무엇인지 모르겠지만 분명히이 문제는 배낭 (여전히 DP 문제)의 범주에 있습니다. 문제 설명에 따르면 일반적으로 0/1 knapsack problem입니다. 따라서 아래의 방정식으로 문제를 해결할 수 있습니다. 여기서 opt[i]은 전체 볼륨이 i 인 백팩에 대해 달성 할 수있는 최대 값을 나타냅니다.

opt[i] = max(opt[i], opt[i - items[j].vol] + items[j].value) 

이 문제는 각 주 항목이 0, 1 또는 2 개의 항목을 가질 수 있다는 점에서 특별합니다. 메인 아이템 M과 두 개의 첨부물 A1 및 A2이 있다고 가정 해보십시오.

• B1, 실제로 M 자체 대신 별도 M, A1, A2을 고려, 우리는 그들에 의해 번들 4 개 항목이 있다는 것을 상상할 수있다. 따라서 B1.volume = M.volume 및 B1.value = M.volume * M.c.
• B2은 M 및 A1 번들입니다. B1.volume = M.volume + A1.volume 및 B1.value = M.volume * M.c + A1.volume * A1.c
• B3은 과 유사하지만 A1을 A2으로 대체하십시오.
• B4은 M, A1, 및 A2으로 구성됩니다. B4.volume = M.volume + A1.volume + A2.volume 및

B4.value = M.volume * M.c + A1.volume * A1.c + A2.volume * A2.c 위의 작업을 수행함으로써, 우리는 번들로 모든 항목을 번역 할 수 있으며, 우리는 이러한 번들을 사용하여 0/1 배낭을 수행 할 수 있습니다.

마지막으로 중요한 것은 동일한 M에 의해 생성 된 번들의 경우에만 B1, B2, B3, 및 B4 중 하나만 선택할 수 있다는 점입니다. 약간의 해킹이 필요할 수 있지만 복잡하지 않아야합니다. :)