[Algorithm] 욕심쟁이 알고리즘 배낭무게 문제풀이 [C++]

[개념과 원리]

최대 용량 M인 하나의 배낭과 n개의 물체가 있고, 각 물체 i에는 물체의 무게 wi와 해당 물체를 배낭에 넣었을 때 얻을 수 있는 이익 pi가 부여되었다고 가정한다. 배낭(kanpsack) 문제는 배낭의 용량을 초과하지 않는 범위 내에서 배낭에 들어 있는 물체의 이익의 합이 최대가 되도록 물체를 넣는 방법을 찾는 문제이다. 여기서는 물체를 쪼개서 넣을 수 있다고 가정한다.

 

 

 

[코드]

#include <iostream>
using namespace std;
 
int main() {
 
    int M = 10; // 배낭의 무게
    int n = 4; // 물건의 개수
    int p[4] = { 14, 15, 20, 9 }; // 물체 i의 이익
    int w[4] = { 4, 3, 5, 3 }; // 물체 i의 무게
    double result[4]; // 무게 / 이익 로 나눈 결과 (소수점 포함하기 위해서)
    int rangking[4]; // 1kg당 단위 이익이 랭킹 부여
    int x[4]; // 배낭에 들어간 물체 i의 비율
 
    for (int i = 0; i < n; ++i) {
        result[i] = (double)p[i] / (double)w[i];
        rangking[i] = 0;
        x[i] = 0;
    }
 
    for (int i = 0; i < n; ++i) {
        int rank = 1;
        for (int j = 0; j < n; ++j) {
            if (result[i] < result[j]) {
                rangking[i] = rank++;
            }
        }
    }
 
    int r = M;
    int totalBenefit = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (i == rangking[j]) {
                if (w[j] < r) {
                    r -= w[j];
                    totalBenefit += p[j];
                }
                else {
                    double num = (double) p[j] / (double) w[j];
                    totalBenefit += (r * num);
                    r -= r;
                }
                if (r == 0) break;
            }
        }
    }
 
    // 가방에 들어간 최대 이익
    cout << "totalBenefit :: " << totalBenefit << endl;
 
    return 0;
}

 

 

 

 

 

 

 

 

베타존 : 네이버쇼핑 스마트스토어