Algorithm Explained: Get the max items you can purchase with a fixed budget

Problem statement: Given a fixed budget and a list of item prices. What is the max number of items you can purchase? You can only buy each item once.

Note: This is the Mark and Toys problem from HackerRank.

Example:

You’re given $10 and a list of items to choose from:

  • A cool coffee cup for $10.
  • A pack of pencils for $2.
  • A notebook for $8.

The max number of items you can buy is 2 (the $2 pencils and the $8 notebook).

Approach

The brute force approach to this problem is to look at all possible combinations of prices. We have N prices. Start by looking at the sum of all N prices. If it’s over budget, look at all combinations with N – 1 prices. And so on. In the worst case, we’d be looking at 2^N – 1 combinations of prices, which means the time complexity is O(2^N). It’s hard to get much worse than that.

Note: 2^N – 1 = (N choose 1) + (N choose 2) + … + (N choose N).

Get greedy

We don’t need to look at all combinations of prices. Instead, we can use a greedy algorithm approach. When we buy an item, it is no longer available, and we subtract it from the budget. To maximize the number of items purchased, we keep buying the cheapest item available until the budget runs out (or when there’s no more available items).

Here’s a step-by-step example of running this algorithm:

budget = 10 prices = [10, 2, 8] iteration 1 2 is the lowest price in [10, 2, 8] subtract 2 from budget, leaving 8 remaining remove 2 from available prices iteration 2 8 is the lowest price in [10, 8] subtract 8 from budget, leaving 0 remaining There's no budget remaining, so return the number of items purchased.
Code language: plaintext (plaintext)

How do we look for the lowest price in each iteration? Since we’re dealing with an unordered list, we have to loop through the list of available prices to find it. Since we have N items, we’ll loop over each item N times, resulting in a time complexity of O(n^2). This is far better than the brute force O(2^N) approach.

Note: Items can’t be partially purchased. Their price must be fully covered by the remaining budget. For example, if you have $5 remaining, you can’t buy a $10 item. This is an edge case to test for.

Optimize by sorting

Instead of searching for the lowest price each iteration, we can optimize by sorting the initial prices in ascending order. We’ll use a built-in sorting function.

This means when we’re looping through the prices, we’re always dealing with the lowest available price. When we can’t buy an item, we know we can’t buy any of the remaining items either, so we can exit early.

Sorting has a worst case time complexity of O(N log N). After sorting, we simply have to loop through the prices until the budget runs out. This means we only have to loop over the items once – a time complexity of O(N).

At the end our algorithm now has a time complexity of O(N log N) (you only keep the highest term in Big-O). This is an order of magnitude improvement over the unoptimized O(n^2) approach.

Not only does sorting improve the performance, but it simplifies the logic (because we no longer have to explicitly manage item availability). Sorting can be used like this to simplify problems.

Code

Now we can implement the optimized greedy algorithm approach discussed above.

Algorithm

Here’s the code.

public static int CalcMaxPurchasedItems(int budget, int[] itemPrices) { int itemsPurchased = 0; Array.Sort(itemPrices); foreach(var itemPrice in itemPrices) { budget -= itemPrice; if (budget < 0) break; itemsPurchased++; } return itemsPurchased; }
Code language: C# (cs)

This uses Array.Sort() to sort the initial list of prices. In theory, this has a time complexity of O(N log N). In reality, it is much faster than that because it has optimizations for integer arrays.

Tests

Here are the unit tests that cover the test scenarios discussed:

[TestMethod()] public void Test1Item_WhenBudgetLessThanItemPrice_Returns0() { //arrange var budget = 10; var itemPrices = new int[] { 20 }; //act var maxItemsPurchased = Algorithm.CalcMaxPurchasedItems(budget, itemPrices); //assert Assert.AreEqual(0, maxItemsPurchased); } [TestMethod()] public void Test1Item_WhenBudgetGreaterThanOrEqualToItemPrice_Returns1() { //arrange var budget = 10; var itemPrices = new int[] { 5 }; //act var maxItemsPurchased = Algorithm.CalcMaxPurchasedItems(budget, itemPrices); //assert Assert.AreEqual(1, maxItemsPurchased); } [TestMethod()] public void Test_OnlyCountsItemIfItCanBeFullyPurchased() { //arrange var budget = 10; var itemPrices = new int[] { 5, 6 }; //act var maxItemsPurchased = Algorithm.CalcMaxPurchasedItems(budget, itemPrices); //assert Assert.AreEqual(1, maxItemsPurchased); } [TestMethod()] public void Test_WhenMultipleValidCombos_ChoosesTheMax() { //arrange var budget = 10; var itemPrices = new int[] { 2, 3, 5, 5 }; //act var maxItemsPurchased = Algorithm.CalcMaxPurchasedItems(budget, itemPrices); //assert Assert.AreEqual(3, maxItemsPurchased); }
Code language: C# (cs)

Leave a Comment