냅색 알고리즘 문제 : 가방에 어떻게 넣어야 이득이 최대일까?
12번째 글은, 냅색 알고리즘 문제입니다. 이것도 꽤 여러 종류가 있는데요. 쪼갤 수 있는 물건이냐, 그렇지 못하냐에 따라서, 그리디로 접근을 할 수 있는지, 아니면 dp로 접근해야 하는지가 나뉩니다. 저는 0/1 냅색 문제를 다뤄 보겠습니다. 이것은 물건을 쪼갤 수 없어요. 물건이 n개가 있습니다. 그리고 가방에 넣을 수 있는 무게는 W입니다. 이 때, 가방에 넣을 수 있는 물건들의 최대 이익은 얼마나 될까요? 먼저 기저 조건을 생각해 봅시다. 물건 0개를 넣었을 때, 가방에 넣은 물건의 총 무게는 0, 이익 또한 0일 겁니다. 따라서, dp[0개][용량 0]을 넣었을 때 값은 0입니다. 대충 이런 경우입니다. 만약에 물건 0개를 넣었는데, 가방에 넣은 물건의 총 무게가 x(x>0)라면 이건 어떨까요?..
자료알고/알고리즘
2019. 7. 3. 00:25
최근댓글