# Coin change issue with additional restrictions

I'm working on the coin change problem with specific coins. Which I understand how to solve, but now there is an additional condition, where each coin has a different weight in grams, and I need to find the number of partitions of a specific sum, but that has to be made with a specific total weight.

I have a set of partitions of coin values that give the required total value, and then a separate set of partitions of weights that sum to the required total weight, and the answer is the intersection of those sets over some function that maps values to weights. Is there some kind of way to efficiently do this? Right now I'm doing it by brute force, where I take each element of whichever partition is smaller and then see if it also meets the other condition. But given how large these sets get, that doesn't seem to be very computationally feasible.

Is there a method to quickly find that intersection or a different approach or way to think about this all together?

• It seems like you ought to be able to modify your algorithm for the ordinary change-making problem to deal with this one. Aren't you doing some kind of recursion, memoizing the number of solutions to the sub-problems? Can't you just modify that directly? Aug 30, 2021 at 19:57
• @saulspatz maybe if I add another dimension to my array? I'm not sure Aug 30, 2021 at 21:15
• You'd have to show the algorithm. I don't know what your array is, nor how you use it. Aug 30, 2021 at 22:30
• @saulspatz duh, sorry. I'm using $p(n,m) = p(n, m-1) + p(n-m, m)$ for the regular problem so it's just a 2d array. I added a another dimension for weight and I think it's working. If I make each coin weigh 1 unit, then im getting the same output as number of integer partitions of length k which I can find the correct answers for Aug 31, 2021 at 0:45

If you can use a computer algebra system, this can be handled via generating functions. For example, suppose you want to make \$5 with dimes (2 grams each) and quarters (6 grams each) with a total weight of 106 grams. In the expansion of $$\left(\frac{1}{1-dw^2v^{10}}\right) \left(\frac{1}{1-qw^6v^{25}}\right)$$ you want to find the term with $$w^{106}v^{500}$$. Mathematica, for instance, finds this easily: $$d^{35} q^6 w^{106} v^{500}$$. I.e., 35 dimes and 6 quarters is the combination with weight $$35\cdot2 + 6\cdot6 = 106$$ grams and value $$\3.50 + \1.50 = \5$$. The idea is that, in the first geometric series, $$d$$ measures the number of dimes, $$w^2$$ accounts for each dime's contribution to the total weight, and $$v^{10}$$ takes care of each dime's monetary value. Here are the first few terms of expanding the geometric series for the dimes: $$\frac{1}{1-dw^2v^{10}} = 1 + dw^2v^{10} + d^2w^4v^{20} + d^3w^6v^{30} + d^4w^8v^{40} + d^5w^{10}v^{50} + \cdots$$ It would be tedious to multiply this with the quarters' series by hand, but is easy for a computer. In case it helps, here's the Mathematica command for finding the $$d^{35} q^6$$ solution mentioned above: Coefficient[Series[(1/(1 - d*w^2*v^10)) (1/(1 - q*w^6*v^25)), {v, 0, 500}], w^106*v^500] • oh wow, that's awesome! I assume you could account for even more restrictions by just adding other variables? Aug 31, 2021 at 1:51 • Sure. Say you want to include nickels at 4 grams each. Then you include a factor$1/(1-n w^4 v^5)$. If you mean add more parameters (beyond weight and value), yes, you could add another variable to whatever power in each term. Just realize that you can restrict things so much that there are no solutions. (In my little example, there was a unique 106 gram$5 solution.) Aug 31, 2021 at 2:26