배낭 문제 (Knapsack Problem)

배낭 문제(Knapsack Problem)

 

배낭 문제란 배낭에 담을 수 있는 무게의 최대값이 정해져 있고,

일정한 가치와 무게가 정해져있는 짐들을 배낭에 담을 때,

가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제이다.

 

배낭 문제는 

1) 물건을 쪼갤 수 있는 배낭문제(Fraction Knapsack Problem)와

ex) 설탕, 소금등

2) 물건을 쪼갤 수 없는 배낭문제(0/1 Knapsack Problem)으로 나뉜다.

 

1) 물건을 쪼갤 수 있는 배낭문제의 경우는 가치가 큰 물건부터 담고, 남은 무게 만큼 물건을 쪼개는 방식으로

그리디 알고리즘으로 해결할 수 있다.

 

2) 물건을 쪼갤 수 없는 배낭문제의 경우는 동적계획법(DP, Dynamic Programming)을 활용해 해결할 수 있다

 

출처:https://dheldh77.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B0%B0%EB%82%AD-%EB%AC%B8%EC%A0%9CKnapsack-Problem