LeetCode Solutions Blog

Maximize Total Tastiness of Purchased Fruits

Number: 2570

Difficulty: Medium

Paid? Yes

Companies: LinkedIn

Problem Description

Given two arrays price and tastiness representing the price and tastiness of each fruit respectively, you need to maximize the total tastiness while keeping the total price within maxAmount. Additionally, you can use at most maxCoupons coupons to buy fruits at half price (rounded down). Each fruit can be bought at most once, and a coupon can only be applied once per fruit.

Key Insights

This problem is a variant of the knapSack problem with an extra dimension (coupon usage).
For each fruit you have three choices: skip it, buy it at full price, or buy it using a coupon (if available).
Use dynamic programming to keep track of the maximum tastiness for a given money spent and coupons used.
The state can be defined with two dimensions: money spent (up to maxAmount) and number of coupons used (up to maxCoupons).

Space and Time Complexity

Time Complexity: O(n * maxCoupons * maxAmount) where n is the number of fruits. Space Complexity: O(maxCoupons * maxAmount)

Solution

We can solve this problem using dynamic programming. Define a dp array where dp[c][a] represents the maximum tastiness achievable using c coupons and spending exactly a money, or at most a money (depending on your transitions). Iterate over the fruits and update the dp array for three cases:

Skip the fruit.
Buy the fruit at full price if you have enough money.
Buy the fruit using a coupon if you have at least one coupon left and enough money for half price (computed as price[i] // 2).

The dp transition can be done in reverse order for the cost to ensure each fruit is only used once. This method ensures all valid combinations are evaluated.

Code Solutions

# Python solution using dynamic programming
def maxTastiness(price, tastiness, maxAmount, maxCoupons):
    n = len(price)
    # Initialize dp with dimensions (maxCoupons+1) x (maxAmount+1) with -infinity
    dp = [[-float('inf')] * (maxAmount + 1) for _ in range(maxCoupons + 1)]
    # Base case: zero cost and zero coupon used yields 0 tastiness
    dp[0][0] = 0

    # Process each fruit
    for i in range(n):
        # Get the fruit cost options
        full_cost = price[i]
        coupon_cost = price[i] // 2
        fruit_taste = tastiness[i]
        # Iterate backwards to avoid reuse of fruit
        for used_coupon in range(maxCoupons, -1, -1):
            for current_cost in range(maxAmount, -1, -1):
                if dp[used_coupon][current_cost] != -float('inf'):
                    # Option 1: Buy fruit at full price if within budget
                    new_cost = current_cost + full_cost
                    if new_cost <= maxAmount:
                        dp[used_coupon][new_cost] = max(dp[used_coupon][new_cost], dp[used_coupon][current_cost] + fruit_taste)
                    # Option 2: Buy fruit with coupon if available and within budget
                    if used_coupon < maxCoupons:
                        new_cost_coupon = current_cost + coupon_cost
                        if new_cost_coupon <= maxAmount:
                            dp[used_coupon + 1][new_cost_coupon] = max(dp[used_coupon + 1][new_cost_coupon], dp[used_coupon][current_cost] + fruit_taste)
                    # Option 3: Skip is implicitly handled by not updating dp.
    # Obtain the maximum tastiness among all states
    ans = 0
    for coupons_used in range(maxCoupons + 1):
        ans = max(ans, max(dp[coupons_used]))
    return ans

# Example usage:
print(maxTastiness([10,20,20], [5,8,8], 20, 1))  # Expected output: 13
print(maxTastiness([10,15,7], [5,8,20], 10, 2))  # Expected output: 28