반응형
knapsack
-
Knapsack 배낭 문제카테고리 없음 2020. 4. 11. 19:17
Knapsack 배낭문제는 DP를 이용하여 풀 수 있는 문제이다. 보통 knapsack 문제는 0-1 Knapsack problem를 말하기에 이에대해 이야기 하도록 하겠다. Knapsack 문제는 가방안에 짐들의 가치가 가장 최대가 되도록 하는 문제인데, 각 짐에 대해 2가지 정보가 있다. 각 짐은 value 와 weight를 가지고 있고, value는 해당 짐의 가치이고 weight는 무게라고 생각하면된다. 즉, 주어진 문제에서의 허용 가능한 weight내에서 어떤 짐들을 넣어야 최대의 value를 담을 수 있는지에 대한 문제이다. 좀 더 흥미롭게 도둑이 가방안에 허용된 무게안으로 가장 값이 나가는 물건들로만 훔쳐서 담아가야 한다는 설정을 해보자. 일반적인 다른 물건들보다 보석은 가볍지만 가치가 높기..
반응형