跳转至

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

题目描述

你有两个非负整数数组 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$ 是水果的数量。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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)

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
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];
};

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

评论