[알고리즘] Knapsack Problem(배낭 문제) 풀이 방식 및 1535번 풀이

이번에는 Dynamic programming 기법을 적용하여 풀 수 있는 대표적인 문제인 배낭 문제(Knapsack problem)을 푸는 방법에 대해서 정리하도록 하겠습니다. 일단 Knapsack problem에는 두 가지가 있습니다. 1. Fractional Knapsack problem 2. 0-1 Knapsack problem 이 배낭 문제는 도둑이 배낭에 담을 수 있는 물건의 무게에 한계가 있는 상황에서 각 물건마다 가치가 다를 때, 훔칠 수 있는 물건의 가치가 최대가 되도록 물건을 훔치는 경우를 구하는 문제 같은 유형의 문제들에 해당됩니다. 그렇다면, Fractional, 0-1 knapsack problem은 각각 무엇을 의미할까요? Fractional은 물건을 통째로 훔칠 필요 없이 물건을 일정 비율만큼만 훔칠 수 있는 경우의 배낭 문제를 0-1 문제는 각각의 물건을 훔치는 경우만 또는 훔칠 수 없는 경우만 있을 때의 배낭 문제를 의미합니다. 하나의 예를 들자면, fr...

원문링크 : [알고리즘] Knapsack Problem(배낭 문제) 풀이 방식 및 1535번 풀이