Coin change issue with additional restrictions

Question

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?

Answer 1

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]