C++ 贪心算法解题：加勒比海盗的宝藏

申请指导本题的C++解决方案。

题目描述

最强的加利海航的著名海航军杰博长驻马船长驻马带着他的黑珍玛号海航船表现在一个装满宝财的藏宝洞。藏宝洞里面有N(N≤100)堆金币，第i堆金币的总重量和总价值分别是mi,vi(1≤mi,vi≤100)。黑珍玛号的承重量为T(T≤1000)，并不一定有方法将全部的金币都带走。他想带走尽可能多的价值的金币。所有金币都可以任意分割，分割完的金币重量价值比(&x5c31;是单位价值)不变。请问杰博长最多可以拿走多少价值的金币？

输入描述

第一行两个整数N，T。

下较N行，每行两个整数mi，vi。

输出描述

一个实数表示答案，保留两位小数。

样本1 输入 4 50 10 60 20 100 30 100 15 45 输出 226.67

住：要用结构体，使用贡心算法

内容

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Coin {
    int weight;
    int value;
};

bool compare(Coin c1, Coin c2) {
    double ratio1 = (double)c1.value / c1.weight;
    double ratio2 = (double)c2.value / c2.weight;
    return ratio1 > ratio2;
}

double findMaxValue(vector<Coin>& coins, int totalWeight) {
    sort(coins.begin(), coins.end(), compare);
    
    double maxValue = 0.0;
    for (int i = 0; i < coins.size(); i++) {
        if (totalWeight >= coins[i].weight) {
            maxValue += coins[i].value;
            totalWeight -= coins[i].weight;
        } else {
            maxValue += (double)totalWeight / coins[i].weight * coins[i].value;
            break;
        }
    }
    
    return maxValue;
}

int main() {
    int N, T;
    cin >> N >> T;
    
    vector<Coin> coins(N);
    for (int i = 0; i < N; i++) {
        cin >> coins[i].weight >> coins[i].value;
    }
    
    double maxValue = findMaxValue(coins, T);
    printf("%.2f\n", maxValue);
    
    return 0;
}