3
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ Request for Clarification: what is the point of permute() ? I see what is DOES (i.e. compute the permutations of an ordered sequence) but what I don't understand is the reason behind its use. Is it required by the problem because it isn't in the description...? Do you believe It is required to solve completely? I don't believe that is the case \$\endgroup\$ – DapperDan Apr 3 at 17:14
0
\$\begingroup\$

My understanding of the problem:

You are provided three values:

  1. A budget(the amount of funds you can spend)

  2. A List of Vendor Batch Sizes

  3. A List of Vendor Batch Prices

Promises/Assumptions: the items 2 & 3(the lists) correspond such that for Vendor i, the vendors batch size and price can be found at List.get(i)

NOTE: Your code has a hard-coded assumption that the two lists (budgetQuantities and budgetCosts) are the same size, or at least you never check that this is true or otherwise enforce this requirement.

Goal: determine the maximum affordable quantity based on Vendor and budget information.


There seems to be some superfluous code going on here, so I will try to address that first


Inner Class MaxQuantity

There really isn't any reason to use this. It has only one use: to interact with the internal int value. As both the class and value are public, I can access all the way through: shoppingBudget.MaxQuantity.value. This is generally considered bad. As the class is in all cases just an int, it can be replaced with an internal variable, private int maxQuantity

suggesting removal


The permute function

As mentioned in my comment, this function seems entirely pointless as the problem does not involve permutations; The information is linear in nature, as there is no "mix and match" (i.e. permutation) of Vendor Information (budgetQuantities and budgetCosts)

suggesting removal

Update I appreciate your use of recursion in your permute function, but its a tad confusing. The second set of swapping seems pointless, as by the time you reach it you are simply propagating back up the recursion tree, swapping indeces that we no longer use.

I looked for similar permutation implementations and found this well designed permutation util, which I used for comparison testing of your permutation method.


IntStream There really isn't a need to create an int[] for indices like this. I see it is mostly used in the permute() function, which I have suggested removing, so I will likewise suggest removing this. With a linear solution, it is much easier to create a single int index and increment it as we iterate through the lists, rather than creating an int for every position from 0 to budgetQuantities,size()-1 (the increment approach is also less computationally expensive, especially where memory is concerned)

Update I had to use this in my rework, definitely shouldn't remove


maxQuantity.value = Integer.MIN_VALUE;

Integer.MIN_VALUE is usually a good initial value for a maximum. However, this is not the true minimum of the problem. The absolute minimum items you can purchase is 0, so it makes more sense to initialize your globalMaximum to 0: private int globalMaximum=0;


UPDATED

findSolution is NOT broken

There is a hole in the logic of your findSolution method. You seem to have written your code with the intent that this method will be called many times, and each result will be compared with the global max (based on your use of maxQuantity.value = Math.max(maxQuantity.value, possibleMax); in permute)

However, this method runs across all vendors. Because of this, your int remaining and counter should be inside your for loop, with an int localMaximumToReturn where counter is currently.

To explain further: your current findSolution forEach loop represents each Possible Interaction between Molly and one Vendor, so both the money available and the total number of computers she can buy per transaction are independent. However, in the above code, each loop is interacting with the same funds, which will introduce severe error.

Example: I ran in debug with breakpoints inside the findSolution method, outside the forEach loop, with the following information:

moneyAvailable: 50
budgetQuantities: {20,19}
budgetCosts: {24,20}

Stepping through, the first loop correctly computes that howManyToBut is 2, meaning she can buy 40 computers for 48 dollars. Then you set remaining to 2 with remaining -= 48

This means for the next loop, we get a cost of 20, which is now greater than our remaining 2 so the second cost/quantity maximum is never checked

We have technically hit each index, so we leave the loop and return the counter 40. While this IS the correct answer, we got here by false means. If you switch the order of items in your lists for the first assert, you should see a return of 38, which will break your assertEqual


It is at this point I see the point of permute in that it was scrambling your orders. Since your findSolution would only ever succeed at checking the first index, permute scrambles your orders so that each item gets a shot at being first, so each possible results is compared with the globalMax. While this works, it is incredibly backward, and buggy I highly recommend fixing this bug in findSolution, and remove the no longer needed permute()


With superfluous code removed you should end up with something similar to:

public class ShoppingBudget {
    int globalMax;

    public int budgetShopping(int budget, List<Integer> batchSizes, List<Integer> batchCosts) {
        List<Integer> indeces = new ArrayList<>();
        IntStream.range(0, batchSizes.size()).forEach((num) -> indeces.add(num));
        Collection<List<Integer>> permutations = new Permutations<Integer>().permute(indeces);
        permutations.forEach(
                (permutation) -> checkPermutationMaximum(permutation, budget, batchSizes, batchCosts)
        );
        return globalMax;
    }

    private void checkPermutationMaximum(List<Integer> indeces, int budget, List<Integer> batchSizes, List<Integer> batchCosts) {
        int localMax = 0;
        int remainingCash = budget;

        int i = 0;
        int sz = indeces.size();
        while (i < sz && remainingCash > 0) {
            int currentVendor = indeces.get(i);
            int currentCost = batchCosts.get(currentVendor);
            if (remainingCash >= currentCost) {
                int cashToCostRatio = remainingCash / currentCost;
                remainingCash -= currentCost * cashToCostRatio;
                localMax += cashToCostRatio * batchSizes.get(currentVendor);
            }
            i++;
        }

        if (localMax > globalMax) globalMax = localMax;

    }
}

The above passes all of your assertEqual tests as well as debug scrutiny


Comments on Update

Rather than trying to create the next unvisited permutation at run time (which is your above approach) I adapted a utility to return a Collection of Lists, where each List is a possible permutation of the input. Then I compute and check the maximum for each permutation

\$\endgroup\$
  • \$\begingroup\$ Thanks for the feedback. I've taken your solution to my IDE and it seems the code you posted is perhaps slightly different than the one you used on your IDE. I've added the increment to currentVendor as a last line in the while loop to avoid infinite loop. It still fails the last assertion though: assertEquals(41, sb.budgetShopping(50, List.of(20, 1), List.of(24, 2))); With the initial 50 dollars we can buy 2 batches of 20 at the cost of $24. Our current total is 40 and the balance is $2. Since we still have $2, we can still buy one package from the other vendor, totalling 41. \$\endgroup\$ – fpezzini Apr 4 at 19:34
  • 1
    \$\begingroup\$ Response edited to include the accumulator, thank you for noticing. I was working under the assumption that you could not purchase from more than one vendor. This explains a lot such as your use of permute and perhaps thus your use of IntStream. Expect a complete edit of my answer soon. \$\endgroup\$ – DapperDan Apr 4 at 19:46
  • \$\begingroup\$ Answer Updated, but for postarity I just <s>struckthrough</s> the old review text. \$\endgroup\$ – DapperDan Apr 5 at 16:56
  • \$\begingroup\$ Thanks for your feedback, it's always interesting to see different approaches to a given problem. By the way, I have since found out a much simpler way to generate the permutations, based on an article from baeldung -> baeldung.com/java-array-permutations \$\endgroup\$ – fpezzini Apr 5 at 20:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.