Find a sum equal or greater than given target using only numbers from set

Question

Example 1:

Shop selling beer, available packages are 6 and 10 units per package. Customer inputs 26 and algorithm replies 26, because 26 = 10 + 10 + 6.

Example 2:

Selling spices, available packages are 0.6, 1.5 and 3. Target value = 5. Algorithm returns value 5.1, because it is the nearest greater number than target possible to achieve with packages (3, 1.5, 0.6).

I need a Java method that will suggest that number.

Simmilar algorithm is described in Bin packing problem, but it doesn't suit me. I tried it and when it returned me the number smaller than target I was runnig it once again with increased target number. But it is not efficient when number of packages is huge.

I need almost the same algorithm, but with the equal or greater nearest number.

Similar question: Find if a number is a possible sum of two or more numbers in a given set - python.

Answer 1

First let's reduce this problem to integers rather than real numbers, otherwise we won't get a fast optimal algorithm out of this. For example, let's multiply all numbers by 100 and then just round it to the next integer. So say we have item sizes x₁, ..., x_n and target size Y. We want to minimize the value

k₁ x₁ + ... + k_n x_n - Y

under the conditions

(1) k_i is a non-positive integer for all n ≥ i ≥ 1

(2) k₁ x₁ + ... + k_n x_n - Y ≥ 0

One simple algorithm for this would be to ask a series of questions like

1. Can we achieve k₁ x₁ + ... + k_n x_n = Y + 0?
2. Can we achieve k₁ x₁ + ... + k_n x_n = Y + 1?
3. Can we achieve k₁ x₁ + ... + k_n x_n = Y + z?
4. etc. with increasing z

until we get the answer "Yes". All of these problems are instances of the Knapsack problem with the weights set equal to the values of the items. The good news is that we can solve all those at once, if we can establish an upper bound for z. It's easy to show that there is a solution with z ≤ Y, unless all the x_i are larger than Y, in which case the solution is just to pick the smallest x_i.

So let's use the pseudopolynomial dynamic programming approach to solve Knapsack: Let f(i,j) be 1 iif we can reach total item size j with the first i items (x₁, ..., x_i). We have the recurrence

f(0,0) = 1
f(0,j) = 0   for all j > 0
f(i,j) = f(i - 1, j) or f(i - 1, j - x_i) or f(i - 1, j - 2 * x_i) ...

We can solve this DP array in O(n * Y) time and O(Y) space. The result will be the first j ≥ Y with f(n, j) = 1.

There are a few technical details that are left as an exercise to the reader:

• How to implement this in Java
• How to reconstruct the solution if needed. This can be done in O(n) time using the DP array (but then we need O(n * Y) space to remember the whole thing).