봉황대 in CS

배낭 문제 (Knapsack Problem) 배낭 문제란, 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제이다. 배낭 문제에는 2가지 경우가 있다. 1. 분할 가능 배낭 문제 (Fractional Knapsack Problem) - 짐을 쪼갤 수 있는 경우 2. 0-1 배낭 문제 (0-1 Knapsack Problem) - 짐을 쪼갤 수 없는 경우 짐을 쪼갤 수 있는 경우에는 그리디 알고리즘을 통해 해결할 수 있다. (가치가 가장 큰 물건부터 담고, 남은 무게만큼 물건을 쪼개는 방식) 짐을 쪼갤 수 없는 경우에는 동적 계획법(Dynamic Programming, DP)을 통해 해결할 수 있다. 브..