1. 다중 배낭 문제 0/1 배낭 문제 가 각 물건이 1개씩 있고 배낭에 담느냐 안 담느냐를 선택하는 문제였다면 다중 배낭 문제(Bounded Knapsack Problem)는 각 물건이 1개 이상 있는 경우 배낭의 물건의 가치가 최대가 되게 하는 문제다. 이때 각 물건이 무한히 있지는 않다. 다중 배낭 문제는 이를 0/1 배낭 문제로 변형하여...

1. 0/1 배낭 문제 배낭 문제(Knapsack Problem)는 조합 최적화의 유명한 문제로 간단하게 말하면, 한 여행가가 가지고 가는 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제이다. 이 중 0/1 배낭 문제(0/1 Knaps...