Question

2431. 最大限度地提高购买水果的口味

English Version

题目描述

你有两个非负整数数组 price 和 tastiness，两个数组的长度都是 n。同时给你两个非负整数 maxAmount 和 maxCoupons。

对于范围 [0, n - 1] 中的每一个整数 i:

• price[i] 描述了第 i 个水果的价格。

• tastiness[i] 描述了第 i 个水果的味道。

你想购买一些水果，这样总的味道是最大的，总价不超过 maxAmount。

此外，你还可以用优惠券以 半价 购买水果 (向下取整到最接近的整数)。您最多可以使用 maxCoupons 次该优惠券。

返回可购买的最大总口味。

注意:

• 每个水果最多只能购买一次。
• 一个水果你最多只能用一次折价券。

 

示例 1:

输入: price = [10,20,20], tastiness = [5,8,8], maxAmount = 20, maxCoupons = 1
输出: 13
解释: 可以用以下方法来达到总口味:
- 无优惠券买第一个水果，总价= 0 + 10，总口味= 0 + 5。
- 用优惠券买第二个水果，总价= 10 + 10，总口味= 5 + 8。
- 不购买第三个水果，总价= 20，总口味= 13。
可以证明 13 是所能得到的最大总口味。

示例 2:

输入: price = [10,15,7], tastiness = [5,8,20], maxAmount = 10, maxCoupons = 2
输出: 28
解释: 可以用以下方法使总口味达到 20:
- 不买第一个水果，这样总价= 0，总口味= 0。
- 用优惠券买第二个水果，总价= 0 + 7，总口味= 0 + 8。
- 用优惠券买第三个水果，总价= 7 + 3，总口味= 8 + 20。
可以证明，28 是所能得到的最大总口味。

 

提示:

• n == price.length == tastiness.length
• 1 <= n <= 100
• 0 <= price[i], tastiness[i], maxAmount <= 1000
• 0 <= maxCoupons <= 5

解法

方法一：记忆化搜索

我们设计函数 $dfs(i, j, k)$ 表示从第 $i$ 个水果开始，剩余 $j$ 元钱，剩余 $k$ 张优惠券时，最大的总美味度。

对于第 $i$ 个水果，可以选择购买或者不购买，如果购买，那么可以选择使用优惠券或者不使用优惠券。

如果不购买，那么最大总美味度是 $dfs(i + 1, j, k)$；

如果购买，如果不使用优惠券（需要满足 $j\ge price[i]$），那么最大总美味度是 $dfs(i + 1, j - price[i], k) + tastiness[i]$；如果使用优惠券（需要满足 $k\gt 0$ 并且 $j\ge \lfloor \frac{price[i]}{2} \rfloor$），那么最大总美味度是 $dfs(i + 1, j - \lfloor \frac{price[i]}{2} \rfloor, k - 1) + tastiness[i]$。

最终的答案是 $dfs(0, maxAmount, maxCoupons)$。

时间复杂度 $O(n \times maxAmount \times maxCoupons)$。其中 $n$ 是水果的数量。

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