Find random $n$ combinations of values with a given sum

Question

This problem is described in the related StackOverflow question: Find all combinations of coins when given some dollar value.

I would like generate a list of $n$ combinations of values that sum up to a certain number. For example, these are 3 ways to obtain the number 100 using the values {25, 50}:

25*4
25*2 + 50*1
50*2

To calculate the combinations, I have adapted the recursive algorithm from python found here. My adapted code in Mathematica looks like this:

makeChange[value_Integer, denominations_List, soln_List, nsol_: 0] := 
 Module[{solution = soln, partial},
  If[nsol != 0 ∧ Length[solutions] >= nsol,
   Return[];
   ];
  If[value == 0,
   AppendTo[solutions, solution];
   Return[];
   ];
  If[denominations == {},
   Return[];
   ];
  With[{firstCoin = First@denominations, tail = Rest@denominations},
   With[{n = Floor[value/firstCoin]},
    Do[
     If[n - ix > 0,
      partial = Append[solution, {firstCoin, n - ix}],
      partial = solution
      ];
     makeChange[value - (n - ix)*firstCoin, tail, partial, nsol];
     , {ix, 0, n}];
    makeChange[value, tail, solution, nsol];
    ]
   ]
  ]

And can be called like this:

solutions = {};
makeChange[100, {25, 50}, {}, 3];
solutions // Column

{{25,4}}
{{25,2},{50,1}}
{{50,2}}

Now, the code works ok but I have two major concerns.

1) It is slow when there are a large number of possible combinations. Can the performance be improved, maybe with memoization?

2) As it is, the algorithm is deterministic and will always return the same first $n$ solutions. Can the code be adapted to make it non-deterministic, so the solutions' order would be random? This will be useful when doing statistical analysis on a smaller sample of a very large set of solutions.

Note that I am not looking for solutions that only calculate a number of possible solutions. I need the actual solutions for statistical analysis. I am also not looking just for the optimal solution, I need to be able to calculate all of them.

Update:

Thanks to @Dr.belisarius' and @march's comments, I considered using the built-in IntegerPartitions and FrobeniusSolve.

The performance of IntegerPartitions is quite good with my test problem if the number of solutions is not too large (it uses a lot of memory):

t = Rationalize@{2.3, 3.06, 3.92, 4.1, 5.74, 7.8, 7.5, 8.5, 0.68, 0.72, 0.81, 0.92, 1.02, 1.07, 1.12};

AbsoluteTiming[
 solip = IntegerPartitions[1000/(GCD @@ t), All, t/(GCD @@ t), 100000];
]

{0.882162, Null}

However, FrobeniusSolve is too slow to find even 100 solutions and seems to run forever.

AbsoluteTiming[
 solf = FrobeniusSolve[t/(GCD @@ t), 1000/(GCD @@ t), 100];
]

$Aborted

Both built-in functions are also deterministic.

Answer 1

Use RandomChoice with FindInstance

denom = {penny, nickel, dime, quarter, half, dollar};
value = {.01, .05, .1, .25, .5, 1};

instance[total_, n : _Integer?Positive : 100] :=
 RandomChoice[FindInstance[
   denom.{1, 5, 10, 25, 50, 100} == 
     100 total &&
    (And @@ Thread[denom >= 0]),
   denom, Integers, n]]

instance[1.67]

(*  {penny -> 62, nickel -> 0, dime -> 8, quarter -> 1, half -> 0, 
 dollar -> 0}  *)

denom.value /. %

(*  1.67  *)

instance[1.67]

(*  {penny -> 52, nickel -> 11, dime -> 1, quarter -> 0, half -> 1, 
 dollar -> 0}  *)

denom.value /. %

(*  1.67  *)

instance[2.33, 1000]

(*  {penny -> 78, nickel -> 9, dime -> 1, quarter -> 2, half -> 1, 
 dollar -> 0}  *)

denom.value /. %

(*  2.33  *)