Random Shopping Algorithm

This is a problem I've ran into a number of times yet have never found a happy solution to. I've coined it the "Random Shopping Algorithm", and the set up is as follows:

Given a certain amount of money and presented with a collection of items, each with a different cost, the algorithm should return a random group of items to purchase whose total is the amount of money given.

Just pick items at random until the money is exhausted does not work, as it won't select "many cheap items" as often as it should. For example, consider the case with $20 and two items: A, costing $10; and B, costing $1. There are three possible outcomes:

1. Buy 20 As
2. Buy 10 A and 1 Bs
3. Buy 2 Bs

The algorithm should come up with these three outcomes with equal probability. If you simply select the item to purchase with equal weighting, chances are you will end up with outcome 2 more often than option 1, and rarely see option 3 at all.

Because of this, I tried varying the probably at which each item is selected, hoping to find a point where all three outcomes had an equal chance. That this doesn't work is probably not too hard to see, but the detailed results are shown in fig 1. This means that a simple re-weighting of the items based on their cost is not sufficient, and perhaps the weighting will have to chance as items are purchased.

The brute force method of accomplishing this is to create a comprehensive list of all possible purchase-sets, and then merely select an item at random. This would obviously be very slow and become slower as more items are added, so is not practical for the general case. Starting with this concept may however be helpful in finding a more efficient algorithm.