Problem description:

Molly wants to purchase laptops for her school. Find out how many laptops she can purchase by comparing the vendors available.

Each vendor sells the laptops in batches, with a quantity identifying how many laptops on each batch, and a cost for the whole batch.

Sample input: 50 [20,19] [24,20] That means Molly has 50 dollars to spend. The first vendor has 20 laptops per batch and each batch costs 24 dollars. The second vendor has 19 laptops per batch and each batch costs 20 dollars.

The possible answers are 40 and 38. If she buys from the first vendor, she will spend 48 dollars (24 * 2) and since she’s buying 2 batches the total quantity is 40 (20 * 2).

If however she would buy from the second vendor, the maximum quantity would be 38, since each batch has 19 laptops and she’d run out of money after the second batch.

The final answer is then 40, since 40 is higher than 38.

This seems similar to the Knapsack problem.

My solution is listed below. The permute method is there to generate the possible permutations between the indices. For instance if we have 3 items in the input array the permutations are:

012 021 102 120 201 210

`import static org.junit.Assert.assertEquals; import java.util.List; import java.util.stream.IntStream; public class ShoppingBudget { public static void main(String[] args) { ShoppingBudget sb = new ShoppingBudget(); assertEquals(40, sb.budgetShopping(50, List.of(20, 19), List.of(24, 20))); assertEquals(20, sb.budgetShopping(4, List.of(10), List.of(2))); assertEquals(0, sb.budgetShopping(1, List.of(10), List.of(2))); assertEquals(41, sb.budgetShopping(50, List.of(20, 1), List.of(24, 2))); } private void permute(int start, int moneyAvailable, int[] inputIndices, List<Integer> budgetQuantities, List<Integer> budgetCosts, MaxQuantity maxQuantity) { if (start == inputIndices.length) { // base case int possibleMax = findSolution(inputIndices, moneyAvailable, budgetQuantities, budgetCosts); maxQuantity.value = Math.max(maxQuantity.value, possibleMax); return; } for (int i = start; i < inputIndices.length; i++) { // swapping int temp = inputIndices[i]; inputIndices[i] = inputIndices[start]; inputIndices[start] = temp; // swap(input[i], input[start]); permute(start + 1, moneyAvailable, inputIndices, budgetQuantities, budgetCosts, maxQuantity); // swap(input[i],input[start]); int temp2 = inputIndices[i]; inputIndices[i] = inputIndices[start]; inputIndices[start] = temp2; } } private int findSolution(int[] inputIndices, int moneyAvailable, List<Integer> budgetQuantities, List<Integer> budgetCosts) { int remaining = moneyAvailable; int counter = 0; for (int index : inputIndices) { if (remaining == 0) { break; } int quantity = budgetQuantities.get(index); int cost = budgetCosts.get(index); if (cost <= remaining) { int howManyToBuy = remaining / cost; counter += howManyToBuy * quantity; remaining -= (howManyToBuy * cost); } } return counter; } private int budgetShopping(int n, List<Integer> budgetQuantities, List<Integer> budgetCosts) { int[] inputIndices = IntStream.rangeClosed(0, budgetQuantities.size() - 1).toArray(); MaxQuantity maxQuantity = new MaxQuantity(); maxQuantity.value = Integer.MIN_VALUE; permute(0, n, inputIndices, budgetQuantities, budgetCosts, maxQuantity); return maxQuantity.value; } } class MaxQuantity { int value; } `