Maximize Total Tastiness of Purchased Fruits - Problem

Imagine you're at a premium fruit market where each fruit has a specific price and tastiness rating. You have a limited budget (maxAmount) and want to maximize the total tastiness of fruits you purchase.

Here's the twist: you have discount coupons (maxCoupons) that let you buy certain fruits at half price (rounded down)! Your goal is to strategically use these coupons to get the maximum possible tastiness within your budget.

Input:

price[] - Price of each fruit
tastiness[] - Tastiness rating of each fruit
maxAmount - Your total budget
maxCoupons - Number of discount coupons available

Output: Maximum total tastiness you can achieve

Rules:

Each fruit can be purchased at most once
Each coupon can be used at most once
Coupons reduce price to price[i] // 2

Input & Output

example_1.py — Basic Example

$ Input: price = [3, 1, 2], tastiness = [4, 2, 3], maxAmount = 6, maxCoupons = 2

› Output: 9

💡 Note: We can buy all three fruits using coupons on the expensive ones: fruit 0 with coupon (price 1, taste 4), fruit 1 at full price (price 1, taste 2), and fruit 2 with coupon (price 1, taste 3). Total cost: 1+1+1=3 ≤ 6, total taste: 4+2+3=9

example_2.py — Limited Budget

$ Input: price = [5, 3, 1, 6], tastiness = [8, 4, 2, 5], maxAmount = 4, maxCoupons = 1

› Output: 6

💡 Note: Best strategy: buy fruit 2 at full price (cost 1, taste 2) and fruit 1 with coupon (cost 1, taste 4). Total cost: 1+1=2 ≤ 4, total taste: 2+4=6. We can't afford fruit 0 or 3 even with coupons.

example_3.py — No Coupons

$ Input: price = [2, 4, 1], tastiness = [3, 6, 1], maxAmount = 5, maxCoupons = 0

› Output: 7

💡 Note: Without coupons, we can buy fruit 1 (price 4, taste 6) and fruit 2 (price 1, taste 1). Total cost: 4+1=5 ≤ 5, total taste: 6+1=7.

Constraints

1 ≤ price.length, tastiness.length ≤ 1000
price.length == tastiness.length
0 ≤ price[i], tastiness[i] ≤ 10⁴
0 ≤ maxAmount ≤ 10⁴
0 ≤ maxCoupons ≤ 1000
Each fruit can be purchased at most once
Each coupon can be used at most once

Visualization

Tap to expand

Asked in

G Google 23 a Amazon 31 f Meta 18 ⊞ Microsoft 15

This is a 3D knapsack problem where we optimize across fruits, budget, and coupons. The optimal approach uses dynamic programming with state dp[fruit][budget][coupons] representing the maximum tastiness achievable. For each fruit, we consider three options: skip it, buy at full price, or buy with a coupon, taking the maximum result.

Common Approaches

✓ Brute Force (Try All Combinations)

⏱️ Time: O(3^n) Space: O(3^n)

Generate all possible combinations of fruits to buy and all possible ways to assign coupons to those fruits. For each valid combination (within budget), calculate the total tastiness.

Dynamic Programming (Optimal)

⏱️ Time: O(n × maxAmount × maxCoupons) Space: O(n × maxAmount × maxCoupons)

This is actually a 3D knapsack problem where we need to optimize across three dimensions: which fruits to consider, remaining budget, and remaining coupons. We use dynamic programming to avoid recomputing the same subproblems.

Brute Force (Try All Combinations) — Algorithm Steps

Generate all possible subsets of fruits to purchase
For each subset, try all possible ways to assign coupons
Check if the total cost is within budget
Track the maximum tastiness found

Visualization

Tap to expand

Step-by-Step Walkthrough

Start at root

Begin with first fruit, no cost, no tastiness

Branch into 3 choices

For each fruit: skip, buy full price, buy with coupon

Explore all paths

Recursively explore every combination

Track maximum

Keep track of best tastiness found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int max(int a, int b) {
    return a > b ? a : b;
}

int backtrack(int* price, int* tastiness, int n, int maxAmount, int maxCoupons,
             int index, int currentCost, int currentTaste, int couponsUsed) {
    if (index == n) {
        return currentTaste;
    }
    
    // Don't buy this fruit
    int maxTaste = backtrack(price, tastiness, n, maxAmount, maxCoupons,
                            index + 1, currentCost, currentTaste, couponsUsed);
    
    // Buy at full price
    if (currentCost + price[index] <= maxAmount) {
        maxTaste = max(maxTaste, 
            backtrack(price, tastiness, n, maxAmount, maxCoupons,
                     index + 1, currentCost + price[index], 
                     currentTaste + tastiness[index], couponsUsed));
    }
    
    // Buy with coupon
    if (couponsUsed < maxCoupons) {
        int discountedPrice = price[index] / 2;
        if (currentCost + discountedPrice <= maxAmount) {
            maxTaste = max(maxTaste,
                backtrack(price, tastiness, n, maxAmount, maxCoupons,
                         index + 1, currentCost + discountedPrice,
                         currentTaste + tastiness[index], couponsUsed + 1));
        }
    }
    
    return maxTaste;
}

int maxTastiness(int* price, int* tastiness, int n, int maxAmount, int maxCoupons) {
    return backtrack(price, tastiness, n, maxAmount, maxCoupons, 0, 0, 0, 0);
}

int main() {
    static int price[1000], tastiness[1000];
    char line[10000];
    int n = 0;
    
    // Read price array
    fgets(line, sizeof(line), stdin);
    char* token = strtok(line, ",");
    while (token != NULL) {
        price[n++] = atoi(token);
        token = strtok(NULL, ",");
    }
    
    // Read tastiness array
    fgets(line, sizeof(line), stdin);
    token = strtok(line, ",");
    int i = 0;
    while (token != NULL && i < n) {
        tastiness[i++] = atoi(token);
        token = strtok(NULL, ",");
    }
    
    // Read maxAmount and maxCoupons
    int maxAmount, maxCoupons;
    scanf("%d", &maxAmount);
    scanf("%d", &maxCoupons);
    
    printf("%d\n", maxTastiness(price, tastiness, n, maxAmount, maxCoupons));
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(3^n)

For each fruit, we have 3 choices: don't buy, buy at full price, buy with coupon

✓ Linear Growth

Space Complexity

O(3^n)

Need to store all possible combinations in worst case

⚡ Linearithmic Space

23.1K Views

Medium Frequency

~25 min Avg. Time

847 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Maximize Total Tastiness of Purchased Fruits - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force (Try All Combinations) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler