Maximize Total Tastiness of Purchased Fruits

Problem

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.

Examples

Example 1:

1
2
3
4
5
6
7


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:

1
2
3
4
5
6
7


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

Solution

Method 1 – Dynamic Programming with State Compression

Intuition

The key idea is to use dynamic programming to track the maximum tastiness achievable for each possible amount spent and number of coupons used. For each fruit, we consider three choices: skip, buy at full price, or buy with a coupon (if coupons remain). We update our DP table accordingly, ensuring we never exceed the budget or coupon limit.

Approach

Initialize a 2D DP array dp[amount][coupons] to store the maximum tastiness for each amount spent and coupons used.
Iterate through each fruit:
- For each possible amount and coupon count, consider:
  - Skipping the fruit.
  - Buying at full price (if within budget).
  - Buying with a coupon (if coupons remain and within budget).
Update the DP table for each choice.
After processing all fruits, the answer is the maximum tastiness in the DP table for any amount ≤ maxAmount and coupons ≤ maxCoupons.

Code

 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


class Solution {
public:
    int maxTastiness(vector<int>& price, vector<int>& tastiness, int maxAmount, int maxCoupons) {
        int n = price.size();
        vector<vector<int>> dp(maxAmount + 1, vector<int>(maxCoupons + 1, 0));
        for (int i = 0; i < n; ++i) {
            vector<vector<int>> ndp = dp;
            for (int amt = 0; amt <= maxAmount; ++amt) {
                for (int cpn = 0; cpn <= maxCoupons; ++cpn) {
                    // Buy at full price
                    int p = price[i];
                    if (amt + p <= maxAmount) {
                        ndp[amt + p][cpn] = max(ndp[amt + p][cpn], dp[amt][cpn] + tastiness[i]);
                    }
                    // Buy with coupon
                    if (cpn + 1 <= maxCoupons) {
                        int cp = p / 2;
                        if (amt + cp <= maxAmount) {
                            ndp[amt + cp][cpn + 1] = max(ndp[amt + cp][cpn + 1], dp[amt][cpn] + tastiness[i]);
                        }
                    }
                }
            }
            dp = ndp;
        }
        int ans = 0;
        for (int amt = 0; amt <= maxAmount; ++amt) {
            for (int cpn = 0; cpn <= maxCoupons; ++cpn) {
                ans = max(ans, dp[amt][cpn]);
            }
        }
        return ans;
    }
};

 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


func maxTastiness(price []int, tastiness []int, maxAmount int, maxCoupons int) int {
    n := len(price)
    dp := make([][]int, maxAmount+1)
    for i := range dp {
        dp[i] = make([]int, maxCoupons+1)
    }
    for i := 0; i < n; i++ {
        ndp := make([][]int, maxAmount+1)
        for j := range ndp {
            ndp[j] = make([]int, maxCoupons+1)
            copy(ndp[j], dp[j])
        }
        for amt := 0; amt <= maxAmount; amt++ {
            for cpn := 0; cpn <= maxCoupons; cpn++ {
                p := price[i]
                if amt+p <= maxAmount {
                    if ndp[amt+p][cpn] < dp[amt][cpn]+tastiness[i] {
                        ndp[amt+p][cpn] = dp[amt][cpn]+tastiness[i]
                    }
                }
                if cpn+1 <= maxCoupons {
                    cp := p/2
                    if amt+cp <= maxAmount {
                        if ndp[amt+cp][cpn+1] < dp[amt][cpn]+tastiness[i] {
                            ndp[amt+cp][cpn+1] = dp[amt][cpn]+tastiness[i]
                        }
                    }
                }
            }
        }
        dp = ndp
    }
    ans := 0
    for amt := 0; amt <= maxAmount; amt++ {
        for cpn := 0; cpn <= maxCoupons; cpn++ {
            if ans < dp[amt][cpn] {
                ans = dp[amt][cpn]
            }
        }
    }
    return ans
}

 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


class Solution {
    public int maxTastiness(int[] price, int[] tastiness, int maxAmount, int maxCoupons) {
        int n = price.length;
        int[][] dp = new int[maxAmount + 1][maxCoupons + 1];
        for (int i = 0; i < n; ++i) {
            int[][] ndp = new int[maxAmount + 1][maxCoupons + 1];
            for (int amt = 0; amt <= maxAmount; ++amt) {
                for (int cpn = 0; cpn <= maxCoupons; ++cpn) {
                    ndp[amt][cpn] = dp[amt][cpn];
                }
            }
            for (int amt = 0; amt <= maxAmount; ++amt) {
                for (int cpn = 0; cpn <= maxCoupons; ++cpn) {
                    int p = price[i];
                    if (amt + p <= maxAmount) {
                        ndp[amt + p][cpn] = Math.max(ndp[amt + p][cpn], dp[amt][cpn] + tastiness[i]);
                    }
                    if (cpn + 1 <= maxCoupons) {
                        int cp = p / 2;
                        if (amt + cp <= maxAmount) {
                            ndp[amt + cp][cpn + 1] = Math.max(ndp[amt + cp][cpn + 1], dp[amt][cpn] + tastiness[i]);
                        }
                    }
                }
            }
            dp = ndp;
        }
        int ans = 0;
        for (int amt = 0; amt <= maxAmount; ++amt) {
            for (int cpn = 0; cpn <= maxCoupons; ++cpn) {
                ans = Math.max(ans, dp[amt][cpn]);
            }
        }
        return ans;
    }
}

 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


class Solution {
    fun maxTastiness(price: IntArray, tastiness: IntArray, maxAmount: Int, maxCoupons: Int): Int {
        val n = price.size
        var dp = Array(maxAmount + 1) { IntArray(maxCoupons + 1) }
        for (i in 0 until n) {
            val ndp = Array(maxAmount + 1) { IntArray(maxCoupons + 1) }
            for (amt in 0..maxAmount) {
                for (cpn in 0..maxCoupons) {
                    ndp[amt][cpn] = dp[amt][cpn]
                }
            }
            for (amt in 0..maxAmount) {
                for (cpn in 0..maxCoupons) {
                    val p = price[i]
                    if (amt + p <= maxAmount) {
                        ndp[amt + p][cpn] = maxOf(ndp[amt + p][cpn], dp[amt][cpn] + tastiness[i])
                    }
                    if (cpn + 1 <= maxCoupons) {
                        val cp = p / 2
                        if (amt + cp <= maxAmount) {
                            ndp[amt + cp][cpn + 1] = maxOf(ndp[amt + cp][cpn + 1], dp[amt][cpn] + tastiness[i])
                        }
                    }
                }
            }
            dp = ndp
        }
        var ans = 0
        for (amt in 0..maxAmount) {
            for (cpn in 0..maxCoupons) {
                ans = maxOf(ans, dp[amt][cpn])
            }
        }
        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:
    def maxTastiness(self, price: list[int], tastiness: list[int], maxAmount: int, maxCoupons: int) -> int:
        n = len(price)
        dp = [[0] * (maxCoupons + 1) for _ in range(maxAmount + 1)]
        for i in range(n):
            ndp = [row[:] for row in dp]
            for amt in range(maxAmount + 1):
                for cpn in range(maxCoupons + 1):
                    p = price[i]
                    if amt + p <= maxAmount:
                        ndp[amt + p][cpn] = max(ndp[amt + p][cpn], dp[amt][cpn] + tastiness[i])
                    if cpn + 1 <= maxCoupons:
                        cp = p // 2
                        if amt + cp <= maxAmount:
                            ndp[amt + cp][cpn + 1] = max(ndp[amt + cp][cpn + 1], dp[amt][cpn] + tastiness[i])
            dp = ndp
        ans = 0
        for amt in range(maxAmount + 1):
            for cpn in range(maxCoupons + 1):
                ans = max(ans, dp[amt][cpn])
        return ans

 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


impl Solution {
    pub fn max_tastiness(price: Vec<i32>, tastiness: Vec<i32>, max_amount: i32, max_coupons: i32) -> i32 {
        let n = price.len();
        let ma = max_amount as usize;
        let mc = max_coupons as usize;
        let mut dp = vec![vec![0; mc + 1]; ma + 1];
        for i in 0..n {
            let mut ndp = dp.clone();
            for amt in 0..=ma {
                for cpn in 0..=mc {
                    let p = price[i] as usize;
                    if amt + p <= ma {
                        ndp[amt + p][cpn] = ndp[amt + p][cpn].max(dp[amt][cpn] + tastiness[i]);
                    }
                    if cpn + 1 <= mc {
                        let cp = (price[i] / 2) as usize;
                        if amt + cp <= ma {
                            ndp[amt + cp][cpn + 1] = ndp[amt + cp][cpn + 1].max(dp[amt][cpn] + tastiness[i]);
                        }
                    }
                }
            }
            dp = ndp;
        }
        let mut ans = 0;
        for amt in 0..=ma {
            for cpn in 0..=mc {
                ans = ans.max(dp[amt][cpn]);
            }
        }
        ans
    }
}

 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


class Solution {
    maxTastiness(price: number[], tastiness: number[], maxAmount: number, maxCoupons: number): number {
        const n = price.length;
        let dp = Array.from({ length: maxAmount + 1 }, () => Array(maxCoupons + 1).fill(0));
        for (let i = 0; i < n; ++i) {
            const ndp = dp.map(row => [...row]);
            for (let amt = 0; amt <= maxAmount; ++amt) {
                for (let cpn = 0; cpn <= maxCoupons; ++cpn) {
                    const p = price[i];
                    if (amt + p <= maxAmount) {
                        ndp[amt + p][cpn] = Math.max(ndp[amt + p][cpn], dp[amt][cpn] + tastiness[i]);
                    }
                    if (cpn + 1 <= maxCoupons) {
                        const cp = Math.floor(p / 2);
                        if (amt + cp <= maxAmount) {
                            ndp[amt + cp][cpn + 1] = Math.max(ndp[amt + cp][cpn + 1], dp[amt][cpn] + tastiness[i]);
                        }
                    }
                }
            }
            dp = ndp;
        }
        let ans = 0;
        for (let amt = 0; amt <= maxAmount; ++amt) {
            for (let cpn = 0; cpn <= maxCoupons; ++cpn) {
                ans = Math.max(ans, dp[amt][cpn]);
            }
        }
        return ans;
    }
}

Complexity

⏰ Time complexity: O(n * maxAmount * maxCoupons) — For each fruit, we iterate over all possible amounts and coupon counts.
🧺 Space complexity: O(maxAmount * maxCoupons) — DP table size depends on budget and coupon limits.

Problem#

Examples#

Solution#

Method 1 – Dynamic Programming with State Compression#

Intuition#

Approach#

Code#

Complexity#