Leetcode -1833- Maximum number of ice cream bars

[Blog link]

The path to learning at 🐔

The nuggets home page

[Topic Description

Tony wants to buy some ice cream to cool off the summer heat. N ice cream cakes are newly found in the store, and the array costs with length N represents the price of the ice cream, where costs[I] represents the cash price of the i-th ice cream. Tony: I have coins to spend. I want to buy as many ice creams as possible. I give you the price array costs and cash amount coins. Please calculate and return the maximum amount of ice cream that Tony can buy with cash coins. Note: Tony can buy the ice cream in any order. The sample1: input: costs = [1.3.2.4.1], coins = 7Output:4Explanation: Tony can buy with subscript0,1,2,4The total price of ice cream is1 + 3 + 2 + 1 = 7The sample2: input: costs = [10.6.8.7.7.8], coins = 5Output:0Tony doesn't have enough money to buy any ice cream. The sample3: input: costs = [1.6.3.1.2.5], coins = 20Output:6Tony can buy all the ice cream bars for a total price of1 + 6 + 3 + 1 + 2 + 5 = 18. Costs. Length == n1 <= n <= 105 
 1 <= costs[i] <= 105 
 1 <= coins <= 108Related Topics Greedy array sort 👍23 👎 0

Copy the code

[答 案]

Leetcode topic link

[making address]

Code link

[introduction]

** Idea 1: greedy plus sort

• After sorting, select the first n minimum values and less than Coins
• The strict proof process of this problem can refer to the solution of the problem proved by the big man of The Palace water, I will not be repeated here

public int maxIceCream(int[] costs, int coins) {
            Arrays.sort(costs);
            if (costs[0] > coins) {
                return 0;
            }
            int sum = 0, res = 0;
            for (int i = 0; i < costs.length; i++) {
                if(sum + costs[i] <= coins) { sum += costs[i]; res++; }}return res;
        }
Copy the code

$Time complexity O(nlg_{n} + n)$

Idea 2: Dynamic planning

• The backpack problem can be changed very quickly
• There is a backpack with the capacity of Coins, and the weight of each item is the corresponding value of the Costs array
• The value of each item is 1. Figure out the maximum value of items placed under the premise of satisfying the backpack capacity
• Defining the equation DP [I][j] represents the maximum number of items taken under the premise that the first I items meet the capacity less than or equal to J
• It can be found that dp[I][J] is only related to DP [i-1][j-cost[I]]
• The algorithm found that this kind of greedy sorting is more TLE than the first kind because the number of items is too large

public int maxIceCream(int[] costs, int coins) {
            int[][] dp = new int[costs.length + 1][coins + 1];
            for (int i = 1; i <= costs.length; i++) {
                int weight = costs[i - 1];
                for (int j = 0; j <= coins; j++) {
                    dp[i][j] = j >= weight ? Math.max(dp[i - 1][j - weight] + 1, dp[i - 1][j]) : dp[i - 1][j]; }}return dp[costs.length][coins];
        }
Copy the code

$Time complexity O(n x C) n indicates the number of items and C indicates the size of Coins$