2548. Maximum Price to Fill a Bag

You are given a 2D integer array items where items[i] = [pricei, weighti] denotes the price and weight of the ith item, respectively.

You are also given a positive integer capacity.

Each item can be divided into two items with ratios part1 and part2, where part1 + part2 == 1.

• The weight of the first item is weighti part1 and the price of the first item is pricei part1.
• Similarly, the weight of the second item is weighti part2 and the price of the second item is pricei part2.

Return the maximum total price to fill a bag of capacity capacity with given items. If it is impossible to fill a bag return -1. Answers within 10-5 of the actual answer will be considered accepted.

class Solution {
public:
    double maxPrice(vector<vector<int>>& items, int capacity) {
        vector<array<double,3>> S;
        for(auto item : items) {
            int p = item[0], w = item[1];
            double r = 1. * p / w;
            S.push_back({r,1. * p,1. * w});
        }
        sort(begin(S), end(S));
        double res = 0;
        while(capacity and S.size()) {
            auto [r,p,w] = S.back(); S.pop_back();
            double ma = min(1. * capacity, w);
            capacity -= ma;
            res += r * ma;
        }
        return capacity ? -1 : res;
    }
};