Where it runs
1. The problem
Step 107 took whole meetings and sorted them by earliest end. Here you again choose greedily by a sort key, but the key is different. There is also a new rule that changes the solution: you may take part of an item.
You have a bag that holds a limited total weight, and many goods. Each good has a weight and a value. Examples are gold dust, grain or oil: goods you can scoop or pour out in parts, instead of taking or leaving them whole. You want the largest total value the bag can carry.
Example: a truck that carries 50 kg, and three sacks. The first weighs 10 kg and is worth 60, the second 20 kg and worth 100, the third 30 kg and worth 120. All 60 kg will not fit, but you can pour out part of a sack. Decide what to take, and how much, so the load is worth as much as possible.
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is includedOn LeetCode
LeetCode has no problem that lets you take part of an item. It does test the half that carries over, sorting by value per unit and taking from the top, on problems where every item has the same size or a ratio decides the order.
Every box takes one unit of truck space, so sort the box types by units per box and take boxes from the top until the truck is full.
Sort the bags by how many rocks each still needs and fill the cheapest first. This is the lesson's greedy with the shortfall as the cost.
Sort workers by wage per unit of quality, the lesson's ratio sort, then keep the k smallest qualities in a max-heap as the ratio grows.