101. Maximum Calories within Budget

Maximum Calories within Budget

You are ordering food from DoorDash and selecting items from a menu. You have a fixed budget, and your goal is to get the maximum total calories that can be bought without going over that budget.

You are given:

A list of item prices in dollars.
A list of calorie values for the same items in the same order.
A budget in dollars.

Each menu item may be purchased more than once. You may choose any combination of items as long as the total price does not exceed the budget.

Return the greatest total calories that can be purchased within the budget. If no item can be purchased, return 0.

Method Signatures

Required Method

int maxCalories(List<Integer> prices, List<Integer> calories, int budget)

prices.size() == calories.size()
prices.get(i) is the dollar price of item i
calories.get(i) is the calories value of item i
budget is the maximum total amount in dollars that may be spent
Return the maximum total calories that can be purchased without exceeding budget

Important Notes

The lists prices and calories describe the same menu items by index.
You may buy the same item multiple times.
All prices and the budget are given as integers in dollars.
The result depends only on staying within the budget and maximizing total calories.

Constraints

1 ≤ prices.size() == calories.size() ≤ 200
1 ≤ prices.get(i) ≤ 1000
1 ≤ calories.get(i) ≤ 1000
1 ≤ budget ≤ 10000

Output Format

Return an int representing the maximum calories that can be purchased without exceeding the budget.

Examples

Example 1

maxCalories(prices = List.of(20, 10), calories = List.of(200, 50), budget = 31)
Output: 250
Explanation: Buy item 0 once and item 1 once. Total price = 20 + 10 = 30, which is within the budget 31. Total calories = 200 + 50 = 250.

Example 2

maxCalories(prices = List.of(20), calories = List.of(200), budget = 31)
Output: 200
Explanation: There is only one item. It can be bought once for 20. Buying it twice would cost 40, which exceeds the budget. So the maximum calories is 200.

Example 3

maxCalories(prices = List.of(20, 10), calories = List.of(200, 50), budget = 20)
Output: 200
Explanation: You can either buy item 0 once for 200 calories, or buy item 1 twice for 100 calories. The better choice is 200.

Example 4

maxCalories(prices = List.of(25, 40), calories = List.of(120, 250), budget = 10)
Output: 0
Explanation: No item can be afforded within the budget, so the answer is 0.