Katkat
Back

Maximize Value Under a Budget

AmazonSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to solve a variation of the 0/1 Knapsack problem where items must be selected to maximize total value without exceeding a specific budget constraint.

Problem Statement

You are managing a procurement budget for a set of software licenses. You are given a list of items, where each item is represented as a tuple (cost, value). You have a total budget available. Each item can be selected at most once.

Write a function maximize_license_value(items, budget) that returns the maximum total value you can obtain such that the sum of the costs of the selected items does not exceed the budget.

Input

  • items: A list of tuples (cost, value), where cost > 0 and value > 0.
  • budget: A non-negative integer representing the maximum total cost allowed.

Output

  • The maximum integer value possible.

Examples

Example 1:

items = [(2, 10), (3, 15), (5, 40)]
budget = 6
# Selecting (2, 10) and (3, 15) gives cost 5, value 25.
# Selecting (5, 40) gives cost 5, value 40.
# Result: 40

Example 2:

items = [(1, 5), (2, 10), (3, 15)]
budget = 2
# Selecting (1, 5) and (2, 10) exceeds budget (3 > 2).
# Selecting (2, 10) gives cost 2, value 10.
# Result: 10

Constraints

  • Number of items: 1 <= n <= 1000
  • budget: 0 <= budget <= 1000
  • Costs and values: 1 <= cost, value <= 1000

Edge Cases

  • budget is 0: The result should be 0.
  • items is empty: The result should be 0.
  • All items exceed the budget: The result should be 0.

Hints

Hint 1

Consider whether a greedy approach (e.g., picking the highest value-to-cost ratio) works for this problem, or if you need to explore all combinations.

Hint 2

This is a classic dynamic programming problem where you can define `dp[w]` as the maximum value achievable with a budget `w`.

Hint 3

Use a 1D array of size `budget + 1` and update it iteratively for each item to optimize space complexity to O(budget).

Follow-up questions

  • How would you modify your solution if each item could be selected multiple times (Unbounded Knapsack)?
  • What is the space complexity of your current solution, and can it be further optimized if the budget is very large but the number of items is small?
  • How would the approach change if you were required to track which specific items were selected to achieve the maximum value?