Want to classify project euler problem 31

Question

I was thinking about Project Euler #31 yesterday, quoted below:

In England the currency is made up of pound, £, and pence, p, and there are eight coins in general circulation:

1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p). It is possible to make £2 in the following way:

1£1 + 150p + 220p + 15p + 12p + 31p How many different ways can £2 be made using any number of coins?

This struck me as a version of the knapsack problem with one constraint (total value: 200).

Q: Is this a knapsack problem?

I ask because there is no weight constraint.

If so, if one builds a decision tree to select elements (keeping in mind there are 200 possible 1s and 100 2s, etc., the array gets up to 375 elements, and I think the problem becomes (is?) expontentially large (2**375). (A memoized decision tree which I was experimenting with yesterday took something like 32 million function calls, running in the background, while I did other stuff).

Alternately, my first impulse for this problem was to think about all the different ways that smaller numbers can go into the next larger number and then to look at some combinatoric formulation of the total ways for all numbers. This looks like it would make sense and be an easier way to solve the problem, but it's sort of half-formed in my mind and my hesitance with the combinatorics route is the fact that large factorials get quickly unwieldy.

At any rate, I am new to attempting to classifying problems like this and I am looking for theoretical guidance on extant problems that mirror this one and while I am not really looking for an answer, I am hoping someone can point me towards the types of algorithms typically used in response and I can research those to better understand the problem.

Thanks.

Answer 1

I would not classify this as a knapsack problem, since (as you say) it does not have a weight limit. However, it can be efficiently solved via dynamic programming, which is the same class of algorithms to which knapsack belongs. The question to ask is, “Given $n$ pence and a coin $x\in\{1,2,5,10,50,100,200\}$ where $x \le n$, how many combinations of coins can I form that each sum to $n-x$ using coin values less than or equal to $x$?” This bottoms out at the case of "how many ways can I give back one pence?" I'll leave the details for you to figure out.

Knapsack solves a different problem. Via Wikipedia, "Given a set of items, each with a mass and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible." If this question were phrased in a way that gave each item a mass equal to their worth, and a value directly proportional to their worth (so penny is the least value, £2 is the highest), then we would be solving the "cash register" knapsack problem. That is, how can I give change with the least amount of coins?

Knapsack is a combinatorial optimization algorithm. This problem is pure combinatorics.

Answer 2

Consider the Generating function f(x)=1/((1 - x)(1 - x^2)(1 - x^5)(1 - x^10)(1 - x^20)(1 - x^50)(1 - x^100)*(1 - x^200)); the coefficient of x^200 is 73682. As an asside, remark that substituting (1-q[k] x^k) for (1-x^k) allows you to generate all different solutions to the coin partitioning problem for any total 'n'; f.e. for n=12 the solutions are q[1]^12 + q[1]^10*q[2] + q[1]^8*q[2]^2 + q[1]^6*q[2]^3 + q[1]^4*q[2]^4 + q[1]^2*q[2]^5 + q[2]^6 + q[1]^7*q[5] + q[1]^5*q[2]*q[5] + q[1]^3*q[2]^2*q[5] + q[1]*q[2]^3*q[5] + q[1]^2*q[5]^2 + q[2]*q[5]^2 + q[1]^2*q[10] + q[2]*q[10]