Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/2431.html
2431. Maximize Total Tastiness of Purchased Fruits
Description
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 ofith
fruit.tastiness[i]
describes the tastiness ofith
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 that:
- 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
Solutions
Solution 1: Memoization Search
We design a function $dfs(i, j, k)$ to represent the maximum total tastiness starting from the $i$th fruit, with $j$ money left, and $k$ coupons left.
For the $i$th fruit, we can choose to buy or not to buy. If we choose to buy, we can decide whether to use a coupon or not.
If we don’t buy, the maximum total tastiness is $dfs(i + 1, j, k)$;
If we buy, and choose not to use a coupon (requires $j\ge price[i]$), the maximum total tastiness is $dfs(i + 1, j - price[i], k) + tastiness[i]$; if we use a coupon (requires $k\gt 0$ and $j\ge \lfloor \frac{price[i]}{2} \rfloor$), the maximum total tastiness is $dfs(i + 1, j - \lfloor \frac{price[i]}{2} \rfloor, k - 1) + tastiness[i]$.
The final answer is $dfs(0, maxAmount, maxCoupons)$.
The time complexity is $O(n \times maxAmount \times maxCoupons)$, where $n$ is the number of fruits.
-
class Solution { private int[][][] f; private int[] price; private int[] tastiness; private int n; public int maxTastiness(int[] price, int[] tastiness, int maxAmount, int maxCoupons) { n = price.length; this.price = price; this.tastiness = tastiness; f = new int[n][maxAmount + 1][maxCoupons + 1]; return dfs(0, maxAmount, maxCoupons); } private int dfs(int i, int j, int k) { if (i == n) { return 0; } if (f[i][j][k] != 0) { return f[i][j][k]; } int ans = dfs(i + 1, j, k); if (j >= price[i]) { ans = Math.max(ans, dfs(i + 1, j - price[i], k) + tastiness[i]); } if (j >= price[i] / 2 && k > 0) { ans = Math.max(ans, dfs(i + 1, j - price[i] / 2, k - 1) + tastiness[i]); } f[i][j][k] = ans; return ans; } }
-
class Solution { public: int maxTastiness(vector<int>& price, vector<int>& tastiness, int maxAmount, int maxCoupons) { int n = price.size(); memset(f, 0, sizeof f); function<int(int i, int j, int k)> dfs; dfs = [&](int i, int j, int k) { if (i == n) return 0; if (f[i][j][k]) return f[i][j][k]; int ans = dfs(i + 1, j, k); if (j >= price[i]) ans = max(ans, dfs(i + 1, j - price[i], k) + tastiness[i]); if (j >= price[i] / 2 && k) ans = max(ans, dfs(i + 1, j - price[i] / 2, k - 1) + tastiness[i]); f[i][j][k] = ans; return ans; }; return dfs(0, maxAmount, maxCoupons); } private: int f[101][1001][6]; };
-
class Solution: def maxTastiness( self, price: List[int], tastiness: List[int], maxAmount: int, maxCoupons: int ) -> int: @cache def dfs(i, j, k): if i == len(price): return 0 ans = dfs(i + 1, j, k) if j >= price[i]: ans = max(ans, dfs(i + 1, j - price[i], k) + tastiness[i]) if j >= price[i] // 2 and k: ans = max(ans, dfs(i + 1, j - price[i] // 2, k - 1) + tastiness[i]) return ans return dfs(0, maxAmount, maxCoupons)
-
func maxTastiness(price []int, tastiness []int, maxAmount int, maxCoupons int) int { n := len(price) f := make([][][]int, n+1) for i := range f { f[i] = make([][]int, maxAmount+1) for j := range f[i] { f[i][j] = make([]int, maxCoupons+1) } } var dfs func(i, j, k int) int dfs = func(i, j, k int) int { if i == n { return 0 } if f[i][j][k] != 0 { return f[i][j][k] } ans := dfs(i+1, j, k) if j >= price[i] { ans = max(ans, dfs(i+1, j-price[i], k)+tastiness[i]) } if j >= price[i]/2 && k > 0 { ans = max(ans, dfs(i+1, j-price[i]/2, k-1)+tastiness[i]) } f[i][j][k] = ans return ans } return dfs(0, maxAmount, maxCoupons) } func max(a, b int) int { if a > b { return a } return b }