Hi folks, I have to figure out a way to get 5.1$ using 51grammes of coins. Now, I have done the research and found out the wiegth of each coins i am allowed to use (0.01$, 0.05$, 0.10$, 0.25$, 1.00$, 2.00$). This problem can be reduced to this system of linear equations but im stock there. How can I solve it and get 1 set of values for which the system satisfies? x*0.01$ + y*0.05$ + z*0.10$ + u*0.25$ + v*1.00$ + w*2.00$ = 5.1$ x*2.35g + y*3.92g + z*1.65g + u*4.40g + v*7.00g + w*7.30g = 51g Simply using gaussian reduction won't work because the variables x, y, z, u, v and w have to be integers. Precision doesnt have to be absolute for the weight, i.e. ]50.5; 51.5[.
Methods used for solving simultaneous linear equations are not applicable to systems with less equations than unkowns. You might find some pertient methods using diophantine (not sure of spelling) as a search term.
Dinosaur, you can use Gaussian elimination on a system with more unknowns than equations, you'll either get no solutions or infinitely many (the corresponding homogeneous system always has infinitely many solutions in such a case). The tricky bit here is there are no integer solutions that give exactly 51g and $5.10, but it can be done inside the tolerance (50.5,51.5). You could have a computer do a brute force search. You can greatly limit the number of variables to search by a few simple observations, like the weight restriction means x<=51.5/2.35 and similar for other variables. The dollar restriction means w is less than 2, and similar for the other variables. Use whichever upper bound on a variable is lower, from weight or dollar. Also, x is a multiple of 5 or else you can't sum to $5.10. I can't think of a good way to do this by hand. The above restrictions will still leave quite a few to check, but you can reduce it with some more complicated reasoning. e.g. weight and dollar restrictions can show w=v=0 is impossible as then the lightest way (dimes have the highest $/g ratio outside ones and twos) to get $5.10 is with 51 dimes, well over your weight allowance. Likewise, v=1, w=0 is impossible, etc. This will help, but it might still take some time by hand.
This is what's known as "Integer Programming" in computer science. It's not exactly my field, but it's a branch of what's generally called "Optimization". There are well known methods for solving IP problems, such as constraint solving via half-planes (this is infact what schmoe is doing). Look it up. It's definitely what you're looking for.
I suppose it's cheating to use Excel's Solver tool? (it uses the Optimization methods mentioned by funkstar). There are other optimization software tools around as well. Excel's optimum answer is 1 dime, 1 dollar, 1 two-dollar, and 8 quarters, for 51.15 grams.
