Why is it not “backpack” but “greed”, and why is it correct? | Python theme month

This article is participating in Python Theme Month. See the link to the event for more details

Topic describes

This is the maximum number of 1833 ice cream bars on LeetCode, and the difficulty is medium.

Tag: “greedy”, “sort”

It’s hot in summer. Tony, a little boy, wants to buy some ice cream.

When n ice cream bars are added to the store, the costs[I] of the ice cream bar in the store are the cash price of the ice cream bar.

Tony has coins in cash for consumption, and he wants to buy as many ice cream bars as he can.

Given costs in the price array and cash amount Coins, please calculate and return the maximum number of ice cream bars Tony can buy with cash.

Note: Tony can buy ice cream in any order.

Example 1:

Input: Costs = [1,3,2,4,1], Coins = 7 Output: 4Copy the code

Example 2:

Input: costs = [10,6,8,7,7,8], coins = 5Copy the code

Example 3: Input: costs = [1,6,3,1,2,5] Output: 6 Explanation: Tony can buy all the ice cream for 1 + 6 + 3 + 1 + 2 + 5 = 18.Copy the code

Tip:

• costs.length == n
• 1 <= n <=
  $10^5$
• 1 <= costs[i] <=
  $10^5$
• 1 <= coins <=
  $10^8$

Fundamental analysis

[I]cost[I]cost[I]cost[I]cost[I]cost[I]

But the complexity of “01 backpack” is O(N∗C)O(N* C)O(N* C), where NNN is the number of items (order of magnitude 10,510 ^5105) and CCC is the backpack capacity (order of magnitude 10,810 ^8108). TLE, obviously.

Another way to think about it is that each item that is selected contributes 111 to the answer, and choosing the item with a smaller price first allows us to have as much money left over as possible, and therefore more choices to make in the future.

So an intuitive way to do this is to sort the array of items “from smallest to largest,” and then make purchase decisions “from front to back.”

prove

Intuitively, this kind of greed leads to the maximum number of items to be selected.

Now let’s prove that this is true.

Assume that greedy sequence of thought for [a1, a2, a3,…, an] [a1, a2, a3,…, an] [a1, a2, a3,…, an] (length of NNN), The real optimal solution of the sequence for [b1, b2, b3,…, bm] [b1, b2, b3,…, bm] [b1, b2, b3,…, bm] (MMM) length.

Both sequences are “monotonically increasing sequences”.

The specific scheme corresponding to the optimal solution is not unique, that is, there are a variety of alternative schemes to make the number of items the same.

Therefore, we just need to prove that the two sequences are of the same length.

According to greedy logic, the total cost of the final choice will not exceed coinscoinscoins, so it is at least a legal choice. Naturally n≤mn \ Leq mn≤m, only need to prove n≥mn \ Geq mn≥m, n=mn =mn =m can be proved.

N ≥mn \geq mn≥m is proved by proof by contradiction. If n≥mn \geq mn≥m is not proved, then n

According to the greedy decision, the sequence of items we choose must be a continuous prefix in the “sorted costcostcost array”. And then selecting the next item will exceed the total cost of Coinscoinscoins; And the selection of the real optimal solution is not distributed in the “sorted costcostcost array”.

At this time, we can use “the contribution of each item to the answer is 111, and replace the item with the item with the one with the earlier distribution in the optimal solution, so that the cost will not increase and the answer will not get worse”.

Thus, the real optimal solution is also adjusted to a continuous prefix.

To sum up, through the proof of contradiction
$n \geq m$Set up, combine
$n \leq m$Can be launched
$n = m$.

The greedy solution must have the same length as the optimal solution.

greedy

Sort, make decisions from front to back, until you can’t.

Code:

class Solution:
    def maxIceCream(self, costs: List[int], coins: int) - >int:
        n = len(costs)
        costs.sort()
        ans = 0
        for i in range(n):
            if coins >= costs[i]:
                ans += 1
                coins -= costs[i]
        return ans
Copy the code

• Time complexity: order complexity is O(nlog⁡n)O(n\log{n})O(nlogn); The complexity of getting the answer is O(n)O(n)O(n). O(nlog⁡n)O(n\log{n})O(nlogn)
• Space complexity: sorting complexity is O(log⁡n)O(\log{n})O(logn). O(log⁡n)O(\log{n})O(logn)

The implementation of Arrays.sort uses biaxial sort.

More on the Greedy/Believing in Science series

All “greedy questions” have strict proof; Not “greedy”, need to prove where there will be proof.

Please feel free to eat 🤣 🤣

The last

This is article No.1833 in our “Brush through LeetCode” series, which began on 2021/01/01. As of the start date, there are 1916 questions on LeetCode, some with locks, and we will first brush through all the questions without locks.

In this series of articles, in addition to explaining how to solve the problem, I’ll give you the most concise code possible. If the general solution is involved, the corresponding code template will be provided.

In order to facilitate the students to debug and submit the code on the computer, I set up a related warehouse: github.com/SharingSour… .

In the repository address, you can see the solution to the series, the corresponding code to the series, the LeetCode link, and other preferred solutions to the series.