knapsack / greedy

#include<bits/stdc++.h>
using namespace std;
int weight[1000000],val[1000000];
double uval[1000000];
int main() {
    int n,mx=20;
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
        scanf("%d %d",&weight[i],&val[i]);

    for(int i=1; i<=n; i++)
        uval[i]=val[i]/(weight[i]*1.0);


    for(int i=1; i<n; i++) {
        for(int j=i+1; j<=n; j++) {
            if(uval[i]<uval[j]) {
                swap(uval[i],uval[j]);
                swap(weight[i],weight[j]);
            }
        }
    }

    double sum=0;
    for(int i=1; i<n; i++) {
        if(weight[i]<=mx) {
            sum+=weight[i]*uval[i];
            mx-=weight[i];
        } else {
            sum+=mx*uval[i];
            break;
        }
    }
    printf("%d\n",sum);
    return 0;
}