1

The office supply store sells your favorite types of pens in packages of 5, 8 or 24 pens. Thus, it is possible, for example, to buy exactly 13 pens (with one package of 5 and a second package of 8), but it is not possible to buy exactly 11 pens, since no non-negative integer combination of 5's, 8's and 24's add up to 11. To determine if it is possible to buy exactly n pens, one has to find non-negative integer values of a, b, and c such that

5a + 8b + 24c = n

Write a function, called numPens that takes one argument, n, and returns True if it is possible to buy a combination of 5, 8 and 24 pack units such that the total number of pens equals exactly n, and otherwise returns False.

Note: it was a question that came up in a mid sem exams, that was last month. i was unable to solve it but am still looking for the solution. any help will be accepted. the code in python or an algorithm to solve it. thanks

Raphael Kwami
  • 13
  • 2
  • http://stackoverflow.com/questions/1642357/simplest-way-to-solve-mathematical-equations-in-python – Vorsprung Apr 21 '13 at 19:24
  • This is a straightforward variant of the knapsack problem. – Cairnarvon Apr 21 '13 at 19:25
  • This is modulus/division math, just need to do checks for if N greater then 24, N % 24 = remainder; if remainder > 8, N % 8 = remainder; if remainder > 5, N % 5 = remainder; return remainder == 0 – David Apr 21 '13 at 19:27
  • @David: If I understand your algorithm correctly, then it's wrong. Consider N = 25. Your algorithm will conclude that there's no solution (since it grabs a 24-pack, but then fails to find a 1-pack), when in fact 5+5+5+5+5=25 is a solution. – Jeremy Roman Apr 21 '13 at 19:34
  • @JeremyRoman yeah just tested in Idle and caught that, >= for comparison would work. Also few other edges remain ( what if N <= -1, etc ) – David Apr 21 '13 at 19:36
  • Changing which comparison to `>=`? I don't see how that fixes your problem. There's a reason UKP is typically solved with DP and not your algorithm (which is much faster, obviously – for the cases where it works, of which [5,8,24] is not one). It's NP-complete. – Jeremy Roman Apr 21 '13 at 19:39
  • @JeremyRoman dumped what I wrote in IDLE into an answer, it appears to work across a range of 1-100 without fault ( I haven't done the math by hand though, just spot checked ). – David Apr 21 '13 at 19:46
  • @JeremyRoman As mentioned in answer, NP problems are deceptive – David Apr 21 '13 at 19:54

1 Answers1

3

This sounds like a good candidate for dynamic programming.

def numPens(n):
  pen_sizes = [5, 8, 24]
  results = [True]
  for i in range(1, n+1):
    results.append(any(i >= size and results[i - size] for size in pen_sizes))
  return results[n]

The key insights here are:

  1. 0 pens can be achieved (trivially: 0 packs of each size).
  2. We can figure out whether we can get n pens if we already know the answers for fewer than n pens.

For example, let's say we want to know whether we can get 10 pens, supposing we already know the answers for 0 through 9. Well, we'll need at least one pack to do so. Then there are 3 cases to consider:

  1. Pack of 5 + however we get 5 pens, if it's possible to get 5 pens.
  2. Pack of 8 + however we get 2 pens, if it's possible to get 2 pens.
  3. Pack of 24 + however we get -14 pens, if it's possible to get -14 pens.

The last of these is nonsensical, so getting 10 pens is possible if (and only if) it is possible either to get 5 pens or to get 2 pens. Since we have assumed we already know the answers for 0 to 9, we can solve the problem (it turns out that 5 pens is possible, as a pack of 5, so we conclude that 10 is as well).

So in order to put ourselves in the situation where we always have the answers for the smaller values of n, we start with the obvious answer for 0. Then we compute the answer for 1 (since we have the answer for 0 already, we can do this). Then we compute the answer for 2 (since we have 0 and 1 already, we can do this), and so on, until we have the answer for the n we want.

This bit of code encapsulates the actual calculation of the result from the previous results: it produces True if there is any pack size size for which it makes sense to buy a pack of that size (without getting a negative number for i - size), and we have previously found a way to buy i - size pens.

any(i >= size and results[i - size] for size in pen_sizes)

The rest of the code simply lets us store that result in the results list for future use, and ultimately return the final result.

Jeremy Roman
  • 16,137
  • 1
  • 43
  • 44
  • it works like magic but the sad thing is i don't understand what's going on, i mean the algorithm. thanks for the solution – Raphael Kwami Apr 21 '13 at 22:47