문제
n개의 물건이 각 무게와 가치를 가지고 있을 때, 한정된 용량의 배낭에 최대 가치를 갖도록 배낭에 넣을 물건들을 정하는 문제.
물건의 전체를 넣지 못한다면 물건을 부분적으로 담는 것을 허용된다.
해결 방법
단위 무게당 가장 값나가는 물건을 배낭에 넣고 계속해서 그 다음으로 값나가는 물건을 넣는다.
만일 물건을 통째로 배낭에 넣을 수 없으면 배낭에 넣을 수 있을 만큼만 물건을 부분적으로 배낭에 담는다.
수행 과정
배낭의 최대 용량 = 40
단위 무게당 가치로 정렬
물건 가치 무게 단위 그램당 가치
백금 60만원 10g 6만원
금 75만원 15g 5만원
은 10만원 25g 4천원
주석 1만원 10g 1천원
백금을 통째로 담는다.
배낭의 무게 = 10/40
가치 = 60만원
금을 통째로 담는다.
배낭의 무게 = 25/40
가치 = 135만원
은을 통째로 담으려 하지만 50이 되어 배나 용량이 초과하게된다.
은을 15만큼만 담는다.
4000 * 15 = 6만원
배낭의 무게 = 40/40
가치 = 141만원
시간 복잡도
O(n log n)