[1][Knapsack][배낭 빈틈없이 채우기 문제] (Fractional Knapsack Problem)

배낭 문제

배낭문제는 n개의물건이 있고 각각 무게와 가치가 주어질때, 물건을 m이하의 무게로 담을때 가능한 최대 가치를 구하는 문제이다.

 

이 배낭 문제는 크게 3가지로 분류된다.

 

• 배낭 빈틈없이 채우기 문제 ( Fractional Knapsack Problem)
• 0/1 배낭 문제 (0/1 Knapsack Problem)
• 개수제한 없는 0/1 배낭 문제 (Unbounded Knapsack Problem)

이 중 배낭을 빈틈없이 채우는 문제에 대해 알아보자.

 

---

Fraction Knapsack Problem

배낭 빈틈없이 채우기 문제는 최대 가방무게 이하로 물건을 담을때 가치가 최대로 최게 담아야하는데 

 

단, 물건을 일부만 담을 수도 있다.

 

예를 들어 무게가 10이고 가치가 20인 물건 A를 절반만 담으면 무게가 5고 가치가 10인 물건처럼 담을 수 있다는 의미이다.

 

이 조건 때문에 가치/무게 값으로 값들을 환산해서 가장 무게대비 가치가 높은 물건부터 차례대로 넣고 무게를 초과하게 되는 물건이 생기면 남은 배낭 무게만큼 잘라서 넣으면 된다.

 

 

 

다음 예를 보자.

 

최대로 가방에 담을 수 있는 무게는 20이고 

 

총 4개의 보석이 있고 가치와 무게, 가치/무게값은 다음과 같다.

 

 

 

 

이 보석들을 무게대비 가치가 높은 순으로 담게되면 다음과 같다.

 

 

여기서 노란보석을 담을때 무게가 초과하므로 최대무게에 맞게 절반만 담게되면 최종적으로 55의 가치가 최대 가치가 된다.