Fractional Knapsack Algorithm

당신에게 15kg 만큼 담을 수 있는 배낭이 주어졌다...
그리고 무게도 다르고 값어치도 다른 보물들을 담아야 한다...
가방을 가득 채우면서도 값어치도 최대화 하는 방법이 있을까??

case 1. 값어치가 비싼 품목들만 담는다!!

욕심쟁이 알고리즘에 부합하지만,,,
해당 품목이 값어치도 높은 만큼 무게도 무거워서 다른 진귀한 품목들을 담지 못한다면??

그러면 그것대로 손해일 것이다...

case 2. 무거운거만 담는다!

허리 디스크

case 3. 가성비를 따져가며 담는다.

여기서 가성비란,,, 값어치/무게를 뜻한다...
무게 당 값어치가 얼마나 나가는지....

따라서 우리는 무게 당 값어치를 계산하여 그것을 위주로 sort하고 담아야한다.

풀이

C++ 코드

/*
// 요것은 아이템 구조체. 값어치와 무게
struct Item{
    int value;
    int weight;
};
*/

class Solution {
  public:
    double fractionalKnapsack(vector<int>& val, vector<int>& wt, int capacity) {
        double profit = 0.0; // 초기 값어치를 0.0으로 초기화
        int n = val.size(); // n은 아이템의 개수
        
        vector<pair<int, int>> vec; // vec은 {값, 무게} 페어를 가지는 벡터
        
        // 값 벡터와 무게 벡터의 값들을 페어화하여 vec 벡터에다 푸쉬
        for (int i = 0; i < n; i++){
            vec.push_back({val[i], wt[i]});
        }
        
        // vec을 가성비(value/weight)을 기준으로 하여 decreasing sort
        sort(vec.begin(), vec.end(), [&](auto a, auto b){
            return (double(a.first) / double(a.second)) > (double(b.first) / double(b.second)); 
        });
        
        // ele가 vec 벡터를 순회
        for(auto ele : vec){
        	// 해당 아이템의 무게가 현 용량을 초과하지 않는다면...
            if( ele.second <= capacity){
                capacity -= ele.second; // 그 아이템 배낭에 쳐박아버려~~
                profit += ele.first; // 값어치도 늘어나버려~~
            }
            // 아이템 무게가 용량을 초과한다면 쪼개기 작업 수행
            else{
                double vpw = double(ele.first) / double(ele.second); // value per weight (값 / 무게)
                profit += capacity * vpw; // 현재 값어치 += 남은 용량 * vpm
                break;
            }
        }
        
        return profit; // 값어치를 리턴해요
        
    }
};

수도코드

function fractionKnapsack(lists, cap){
	for list in lists{
    	list.vpm = list.value / list.weight;
	}
    
    sort lists in decreasing order
   	
    double profit = 0.0;
    
    for list in lists{
    	if (list.weight <= cap){
        	cap -= list.weight;
            profit += list.value;
        }
        else{
            profit += list.vpm * cap
            break;
        }
    }
    return profit;
        	
}