1
$\begingroup$

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)

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

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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 $\endgroup$
    – Julien
    Nov 8, 2023 at 10:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.