Algorithm

[알고리즘] Knapsack Problem(배낭 문제)

정의 Knapsack Problem은 일정 무게를 담을 수 있는 배낭 안에 담을 수 있는 물건의 총량을 최적화 하는 문제이다. 배낭의 크기, 물건의 개수, 각 물건의 무게와 가치가 주어질 때, 배낭에 넣을 수 있는 물건들의 가치가 최대가 되게 하는 조합을 찾는 문제이다. Knapsack Problem은 크게 0-1 Knapsack Problem과 Fractional Knapsack Problem으로 나뉜다. Knapsack Problem의 예제는 백준 문제 12865번. 평범한 배낭 문제를 풀었다. 0-1 Knapsack Problem 물건을 쪼개 배낭에 넣을 수 없을 때, 각 물건을 배낭에 넣을 지 말지 결정하는 문제. Dynamic Programming으로 문제를 해결할 수 있다. 접근 방식 Data..