Method 1 – Greedy (Fractional Knapsack)

Intuition

To maximize the total price, always take as much as possible from the item with the highest price per unit weight. This is the classic fractional knapsack problem, where we can take fractions of items.

Approach

For each item, calculate its price per unit weight.
Sort the items in descending order of price per unit weight.
Initialize ans = 0 and iterate through the sorted items:
- If the current item's weight is less than or equal to the remaining capacity, take the whole item and add its price to ans.
- Otherwise, take as much as possible (fractional part) to fill the bag and add the proportional price to ans.
- Stop when the bag is full.
If the bag is not filled after all items, return -1. Otherwise, return ans.

Code

[{"language":"C++","code":"class Solution {\npublic:\n    double maximumPrice(vector<vector<int>>& items, int capacity) {\n        vector<pair<double, int>> v;\n        for (auto& it : items) v.push_back({(double)it[0]/it[1], v.size()});\n        sort(v.rbegin(), v.rend());\n        double ans = 0;\n        for (auto& [ratio, idx] : v) {\n            int w = items[idx][1], p = items[idx][0];\n            if (capacity >= w) {\n                ans += p;\n                capacity -= w;\n            } else {\n                ans += ratio * capacity;\n                capacity = 0;\n                break;\n            }\n        }\n        return capacity == 0 ? ans : -1;\n    }\n};","lang":"cpp","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">class</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> Solution</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">public:</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">    double</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> maximumPrice</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">vector</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">&#x3C;</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">vector</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">&#x3C;</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">>></span><span style=\"color:#D73A49;--shiki-dark:#F97583\">&#x26;</span><span style=\"color:#E36209;--shiki-dark:#FFAB70\">

Related Tags