I’m trying to find an algorithm for this problem. Ideally in ruby but any language would also be great:

I’m going to the shop and need to buy X grams of an ingredient.

The shop does not necessarily have an “X grams of ingredient” product. But they have N products with different weights.

Which combination of products should I buy so I end up with at least X grams of the ingredient and the cheapest total price? I can select the same product several times.

For example :

I want to buy 80g of rice. The shop has these products:

• Product A: 50g of rice for $2
• Product B: 75g of rice for $2.5
• Product C: 150g of rice for $3

Solution: I need to buy 1 product C. I end up with 70g more than I need but it’s the cheapest option to get at least 80g.