부분배낭

배낭 (Knapsack) 문제 n개의 각각 무게와 가치를 지닌 물건을 최대의 가치를 갖도록 배낭에 넣는 문제 부분 배낭 (Fractional Knapsack) 문제 물건을 나눠서 담는 것을 허용 그리디 사용 가능 0-1 배낭 문제 물건을 통째로 배낭에 넣어야 함 동적 계획 알고리즘, 백트래킹 기법, 분기 한정 기법으로 해결 부분 배낭 문제 그리디 알고리즘 Pseudo code FractionalKnapsack(n, weightAndPriceList, C) Input 물건 n개 각 물건의 무게와 가치 배낭의 용량 C Output 배낭에 담은 물건 리스트 L 배낭에 담은 물건 가치의 합 v 1. 각 물건에 대해 단위 무게 당 가치를 계산 2. 물건들을 단위 무게 당 가치를 기준으로 내림차순으로 정렬하고, 정..