Let’s take a last stab at our beer-delivery problem. We tried out a Sieve, we used the Microsoft Solver – time for some recursion.

How can we organize our recursion?

If we had only 1 type of beer pack, say, 7-packs, the best way to supply n bottles of beer is to supply the closest integer greater than n/7, that is, $$\lceil {n \over 7} \rceil$$

If we had 7-packs and 13-packs, we need to consider multiple possibilities. We can select from 0 to the ceiling of n/7 7-packs, and, now that we have only one type of case pack left, apply the same calculation as previously to the remaining bottles we need to supply – and select the best of the combinations, that is, the combination of beer packs closest to the target.

If we had even more types of beer packs available, we would proceed the same way, by trying out the possible quantities for the first pack, and given the first, for the second, and so on until we reach the last type of pack – which is pretty much the outline of a recursive algorithm.

More...

In our last post, we looked at a Sieve-like algorithm to help a Brewery find how closely they can match the number of beer bottles their thirsty customers desire, using only 7-packs and 13-packs of delicious beer; in less appetizing but more precise terms, we are trying to solve the following problem:

Suppose that you are given a list of integers, and a target integer. Your goal is to find the closest value that is greater or equal to the target, by combining integers (“packs”) from the list (only positive combinations are allowed). For instance, given 3 and 5, the closest you can get to 16 would be 5 x 2 + 3 x 2 = 16, and the closest to 17 would be 3 x 6 = 18.

The Sieve solution is pretty effective, but has some limitations. Today, we’ll take another approach: leveraging the Microsoft Solver Foundation.

The beauty of the Solver is that it allows you to focus on what you want to achieve, rather than on how to achieve it. As long as you can define clearly what your goal, your decision variables and your constraints are, you can leave it to the Solver engine to figure out what the best way to achieve that goal is, by searching the best values for the Decision variables you defined.

So what are we trying to achieve here? Our goal, in Solver terms, is to minimize the extra number of bottles shipped, under the constraint that the number of bottles shipped is greater than the requested target number. Our Decision variables are the number of units of each Beer Pack we will ship, with a constraint that Decisions must be integer (we cannot ship half-packs), and positive.

Let’s add a reference to the Solver in our project (details here), and see how this looks like in code:

More...

In my last post, I presented a small problem which I found interesting: how to help a Brewery of the glorious land of Bizzarostan in finding the perfect combination of 7-packs and 13-packs of beer. Or, in more serious terms,

Suppose that you are given a list of integers, and a target integer. Your goal is to find the closest value that is greater or equal to the target, by combining integers (“packs”) from the list (only positive combinations are allowed). For instance, given 3 and 5, the closest you can get to 16 would be 5 x 2 + 3 x 2 = 16, and the closest to 17 would be 3 x 6 = 18.

My first take on the problem was inspired by the Sieve of Eratosthenes. The idea is to accumulate in a list all possible combinations of packs, and take the smallest combination greater than the target. The main difference with the Sieve of Erathostene is that for prime numbers, we only care about listing numbers that are multiples of primes, whereas here we need to enumerate linear combinations of packs, and not simply all the multiples of single packs.

For instance, in the example where we search for a target of 16 using a combination of 3- and 5-packs, the procedure looks like:

* Add 0 to the combinations, i.e. {0}

* Add the multiples of 3, until 17 is reached, i.e. {0, 0 + 3 x 1, 0 + 3 x 2 = 6, 9, 12, 15, 18}

* For each element of the list, create multiples of 5, and progressively add them to the list, i.e.

{0, 3, 6, 9, 12, 15, 18, 0 + 5, 0 + 2 x 5, 0 + 3 x 5, 0 + 4 x 5, 3 + 5 x 1, 3 + 5 x 2, 3 + 5 x 3, 6 + 5 x 1, … }

Note that we need to accumulate all the intermediate combinations, and cannot simply store the first number greater than the limit for each pack, because we need to consider solutions which combine multiple packs – like 16 = 3 x 2 + 5 x 2

More...