배낭 문제(knapsack) 냅색 알고리즘

[Algorithm] 배낭 문제(knapsack) 냅색 알고리즘

배낭 문제(knapsack) 냅색 알고리즘이란 Knapsack Problem, 배낭문제는 다이나믹 프로그래밍에서 매우 유명한 문제이다. 조합 최적화(Combination Optimization) 문제 중 하나로, 주어진 공간(배낭)에 최대 가치를 가지는 물건들을 선택하는 문제이다. 일반적으로 배낭에 넣을 수 있는 총 무게(용량)가 주어지고, 물건의 무게와 해당 물건을 배낭에 넣을 때의 가치가 주어진다. 배낭 문제에는 크게 2가지의 유형이 있다. 0/1 배낭 문제(0/1 Knapscak Problem) 이 유형에서는 각 물건을 배낭에 넣을지(1) 또는 넣지 않을지(0)를 결정해야한다. 즉, 각 물건은 배낭에 한 번만 들어갈 수 있다. 이러한 제약 때문에 0/1 이라는 이름이 붙었다. 이 유형의 배낭 문제는..