source: https://leetcode.com/problems/maximize-total-tastiness-of-purchased-fruits/description/
Maximize Total Tastiness of Purchased Fruits
You are given two non-negative integer arrays price and tastiness, both arrays have the same length n. You are also given two non-negative integers maxAmount and maxCoupons.
For every integer i in range [0, n – 1]:
- price[i] describes the price of ith fruit.
- tastiness[i] describes the tastiness of ith fruit.
You want to purchase some fruits such that total tastiness is maximized and the total price does not exceed maxAmount.
Additionally, you can use a coupon to purchase fruit for half of its price (rounded down to the closest integer). You can use at most maxCoupons of such coupons.
Return the maximum total tastiness that can be purchased.
Note:
- You can purchase each fruit at most once.
- You can use coupons on some fruit at most once.
Example 1:
Input: price = [10,20,20], tastiness = [5,8,8], maxAmount = 20, maxCoupons = 1
Output: 13
Explanation: It is possible to make total tastiness 13 in following way:
- Buy first fruit without coupon, so that total price = 0 + 10 and total tastiness = 0 + 5.
- Buy second fruit with coupon, so that total price = 10 + 10 and total tastiness = 5 + 8.
- Do not buy third fruit, so that total price = 20 and total tastiness = 13.
It can be proven that 13 is the maximum total tastiness that can be obtained.
Example 2:
Input: price = [10,15,7], tastiness = [5,8,20], maxAmount = 10, maxCoupons = 2
Output: 28
Explanation: It is possible to make total tastiness 20 in following way:
- Do not buy first fruit, so that total price = 0 and total tastiness = 0.
- Buy second fruit with coupon, so that total price = 0 + 7 and total tastiness = 0 + 8.
- Buy third fruit with coupon, so that total price = 7 + 3 and total tastiness = 8 + 20.
It can be proven that 28 is the maximum total tastiness that can be obtained.
Constraints:
- n == price.length == tastiness.length
- 1 <= n <= 100
- 0 <= price[i], tastiness[i], maxAmount <= 1000
- 0 <= maxCoupons <= 5
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
class Solution { public int maxTastiness(int[] price, int[] tastiness, int maxAmount, int maxCoupons) { int[][][] memo = new int[price.length+1][maxAmount+1][maxCoupons+1]; for(int[][] m: memo){ for(int[] n: m){ Arrays.fill(n, -1); } } return dfs(price, tastiness, maxAmount, maxCoupons, 0, memo); } private int dfs(int[] price, int[] tastiness, int amount, int coupons, int index, int[][][] memo) { if(index >= price.length){ return 0; } if(memo[index][amount][coupons]!=-1) return memo[index][amount][coupons]; int max = Integer.MIN_VALUE; //if there is a coupon left and half of the price of an item is less than the amount left //then add that item if(coupons > 0 && amount >= price[index]/2){ max = Math.max(max, tastiness[index] + dfs(price, tastiness, amount-(price[index]/2), coupons-1, index+1, memo)); } //if there is no coupon left but you still have enough money to pay for an item //then add that item if(amount >= price[index]){ max = Math.max(max, tastiness[index]+dfs(price, tastiness, amount-price[index], coupons, index+1, memo)); } //otheriwse leave the item max = Math.max(max, dfs(price, tastiness, amount, coupons, index+1, memo)); memo[index][amount][coupons] = max; return max; } } |