I'm trying to find an algorithm for this problem:
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 amount of ingredient the closest to X as possible? I can select the same product several times.
Example 1 :
I want to buy 1.4kg of pasta. The shop has these products:
- Product A: 1kg of pasta
- Product B: 500g of pasta
- Product C: 300g of pasta
Solution: I need to buy 1 product B and 3 products C (500g + 3 x 300g = 1.4kg)
because it's the exact amount I need.
Example 2 :
I want to buy 300 grams of rice. The shop has these products:
- Product A: 1kg of rice
- Product B: 500g of rice
- Product C: 200g of rice
Solution: I need to buy 2 products C.
Because it ends up being 400g, which is lighter than 1 product B (2x200g < 500g)