Question

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 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 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:
  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)

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];
};

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)
}