4110:圣诞老人的礼物-Santa Clau’s Gifts（贪心算法）

圣诞节来临了，在城市A中圣诞老人准备分发糖果，现在有多箱不同的糖果，每箱糖果有自己的价值和重量，每箱糖果都可以拆分成任意散装组合带走。圣诞老人的驯鹿最多只能承受一定重量的糖果，请问圣诞老人最多能带走多大价值的糖果。

15
4
8
7
2

1193.0

#include <bits/stdc++.h>
using namespace std;
struct T {
    int v,w;
    double p;
};
bool cmp(T a,T b) {
    return a.p>b.p;
}

int main() {
    int n,m;
    double ans=0;
    cin>>n>>m;
    T t[n];
    for(int i=0; i<n; i++) {
        cin>>t[i].v>>t[i].w;
        t[i].p=t[i].v/t[i].w;
    }
    sort(t,t+n,cmp);
    int i=0;
    while(m>0) {
        if(m-t[i].w>0) {
            ans+=t[i].v;
            m-=t[i].w;
            i++;
        }
        else{
            ans+=t[i].p*m;
            m=0; 
        }
    }
    printf("%.1lf\n",ans);
    return 0;
}