Maximize total tastiness of purchased fruits

Array Dynamic Programming

64.5% acceptance

Mar 31, 2026

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.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

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;
    // dp[j][c] = max tastiness using budget j and c coupons
    let mut dp = vec![vec![0i32; mc + 1]; ma + 1];
    for i in 0..n {
      let p = price[i] as usize;
      let t = tastiness[i];
      let half = p / 2;
      for j in (0..=ma).rev() {
        for c in (0..=mc).rev() {
          // buy without coupon
          if j >= p {
            dp[j][c] = dp[j][c].max(dp[j - p][c] + t);
          }
          // buy with coupon
          if c > 0 && j >= half {
            dp[j][c] = dp[j][c].max(dp[j - half][c - 1] + t);
          }
        }
      }
    }
    dp[ma][mc]
  }
}