# Algorithm for optimal item selections

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)

• What is your COMPUTER SCIENCE question here? Formalise & generalise the examples you work out. What to buy for 4.800 g X? Nov 2, 2023 at 16:31
• Thanks for your comment @greybeard. I edited my question Nov 2, 2023 at 16:59

This problem is NP-Hard by a reduction from the following version of subset sum: given a multi-set $$X$$ of $$2n$$ numbers $$\{x_1, \dots, x_{2n}\}$$ and a target $$T$$, is there a subset $$X'$$ of $$X$$ with $$|X'|=n$$ and $$\sum_{x \in X'} =T$$?

However, the problem admits a pseudopolynomial-time dynamic programming algorithm when all weights are integers.

Let $$OPT[x]$$ be true ($$\top$$) if there is a way to choose a subset of products whose sum of weights is exactly $$x$$, and false ($$\bot$$) otherwise. Clearly $$OPT[0]= \top$$ and $$OPT[x]=\bot$$ for $$x<0$$. Moreover, denoting by $$w_i$$ the weight of the $$i$$-th product, whenever $$x>0$$ you have: $$OPT[x] = \bigvee_{i=1}^N OPT[x-w_i].$$

Each value $$OPT[x]$$ for $$x = 0, \dots, X$$ can be computed in time $$O(N)$$, and hence all such values can be found in time $$O(N \cdot X)$$.

The minimum amount $$X^*$$ that is not smaller than $$X$$ can be found in an additional $$O(N \cdot X)$$ time since either $$OPT[X]=\top$$ (i.e., $$X^* = X$$) or it can be found by adding one more product to some achievable amount $$x$$, i.e., $$X^* = \min_{i=1,\dots,N} \left( w_i + \min_{\substack{x = \max (0, X-w_i+1), \dots, X-1 \\ OPT[x]=\top}} x \right),$$ where we treat a minimum over an empty range as $$+\infty$$.

The actual solution can be found (in the same asymptotic time) by retracing the optimal choices backwards.

• Thanks a lot for your answer @Steven. To be honest, I don't understand anything of what you wrote. I posted the question here hoping to get an algorithm in pseudo code. But thank you so much for taking the time to respond. Hopefully one day I will understand what you wrote. Or someone else will find it useful. In the end, I used this ruby code: stackoverflow.com/a/77444748/265122 Nov 8, 2023 at 10:35