배낭 문제는 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법입니다. 이 배낭 문제는 두 가지로 나누어집니다. 짐을 쪼갤 수 있는 경우인 분할 가능 배낭(Fractional Knapsack) 짐을 쪼갤 수 없는 경우인 0-1 배낭(0-1 Knapsack) 분할 가능 배낭 이 문제는 그리디 알고리즘을 적용하면 다항 시간 안에 풀 수 있습니다. 짐을 쪼갤 수 있는 경우에는 무게당 가치가 제일 높은 물건이 먼저 들어가야 하므로 각 물건의 가치/무게를 구한 다음 가장 높은 물건부터 무게의 최댓값까지 넣습니다. 0-1 배낭 이 문제는 백준 12865번의 예제를 참고하여 설명하겠습니다. 물건을 담았을 때의 가치를 계산할..