greedy knapsack

프로그램 명: knapsack

제한시간: 1 초

도둑이 보석상에 침입하여 보석을 훔쳐가려고 한다. 그런데 도둑이 가져 갈수 있는 보석의 무게(n)은 한정되어 있다.

각각의 보석의 무게(weight)와 값(value)을 가지고 있다. 무게 n 으로 어떤 보석을 가져 가는게 가장 많은 이윤(?)을 취할 수 있는 가를 구하는게 문제이다.

단, 보석은 쪼갤 수 있고 종류당 하나씩 있다고 하자.

입력 방법

입력의 첫 줄에는 도둑이 가져갈 수 있는 무게를, 다음 줄에는 보석의 개수, 다음 줄 부터는 각 보석의 무게와 값이 한 줄에 하나씩 입력된다.

출력 방법

첫 줄에는 최대 이윤을 출력한다. 보석의 개수는 최대 1000 개 까지이고 무게와 가치는 모두 정수값이다.

출력은 소수 3 번째 자리에서 반올림하여 2 자리까지 출력한다.

입출력 예

입력

30

3

5 50

10 60

20 140

출력

220.00

#include <stdio.h>

// a2/a1 과 b2/b1을 비교하여 앞부분이 작다면 

// 즉 a2*b1이 a1*b2보다 작다면 1을 반환하다.

int smaller(int a1, int a2, int b1, int b2) {

    if(a2*b1<a1*b2) return 1;

    else return 0;

} 

int main() {

    // 최대 1000개의 자료를 2개씩 쌍을 지어서 보관한다.

    // 입력받은대로 먼저 받은 수는 무게를 나중 받은수는 이익액을 저장한다.

    int data[2000]={0,};

    // nk는 data에 보관한 자료의 인덱스이다.

    int i, j, k=0, nk;

    // n의 보석의 갯수이다. mx는 최대무게 이다.

    int n, mx, x, y;

    // profit는 최대이익이다.

    double profit=0;

    // 무게를 읽는다.

    scanf("%d", &mx);

    // 보석의 갯수를 읽는다.

    scanf("%d", &n);

    // 보석의 갯수만큼 자료를 읽어 들인다.

    // 2개씩 쌍을 지어 data에 보관한다.

    for(i=0;i<n;++i) {

        scanf("%d%d", &x, &y);

        data[k++]=x;

        data[k++]=y;

    }

    // 보관한 자료의 갯수이다. n의 2배가 된다.

    nk=k;

    // 버블정렬을 한다. 갯수는 nk/2 개이다.

    for(i=0;i<nk;i+=2) {

        for(j=0;j<nk-i-2;j+=2) {

            // 앞부분이 바로 뒤의 값보다 작다면 서로 바꾸어 준다.

            // 이렇게 하면 가장 작은 값이 뒤로 이동하게 된다.

            // 정렬이 끝나면 가장 큰이익을 줄수 있는 보석이 앞부분에 오게 된다.

            // 즉 단위 무게당 이익이 많은 보석이 앞쪽에 오게 된다.

            if(smaller(data[j],data[j+1],data[j+2],data[j+3])) {

                x=data[j]; y=data[j+1]; 

                data[j]=data[j+2]; data[j+1]=data[j+3];

                data[j+2]=x; data[j+3]=y;

            }

        }

    }

    i=0;

    x=0; // 지금까지 선택한 보석의 무게

    // 지금까지 선택한 보석의 무게가 최대무게 보다 작다면

    while(x<mx) {

        // y는 지금 따져볼 보석의 무게이다.

        y=data[i];

        // 지금까지 선택한 보석의 무게와 현재 고려하고 있는 보석의 무게를 더해서 

        // 최대무게 이하이면 무조건 이 보석을 선택한다.

        if(x+y<=mx) {

            x+=y;  // 선택한 보석의 무게는 지금 보석의 무게를 더한 것이 된다.

            profit+=(double)data[i+1]; // 이익도 마찬가지이다.

        }

        // 만약 지금까지 선택한 보석의 무게와 현재 보석의 무게를 더해서

        // 최대무게보다 크게 되면, 현재보석을 잘라야한다.

        // 즉 (mx-x)/y 만큼의 비율로 보석을 잘라야 한다. 여기서y는 현재보석의 무게이다.

        // 이익도 이 비율만큼만 더해진다. 무게는 최대무게가 된다.

        else {

            profit+=(double)data[i+1]*(double)(mx-x)/(double)y;

            x=mx;

        }

        // 다음 보석을 고려하기 위해서 인덱스를 2를 증가시킨다.

        i+=2;

    }

    // 최종이익이다.

    printf("%.3f", profit);

    return 0;

}