1
$\begingroup$

I have the following problem and would like an orientation on which algorithms I can try to adapt to solve it in the best possible way.

SCENARIO

A company has a warehouse where it stores several products. A product can be stored in several packages, for example:

1 box with 10 units

1 box with 3 boxes of 10 units

1 box with 30 units

1 box with 5 boxes of 30 units

Eventually these products need to be dispatched for consumption in the company's stores. Each store makes its own request for products according to their needs.

However, such requests do not take into account the available packaging, ie the quantity requested may or may not coincide with the quantity of a particular packaging.

Example:

1 box with 8 lunits

2 boxes with 2 units

1 box with 4 units

1 box with 6 units

The store could request 13 units of product, and thus there would be no packaging combination that could total exactly 13 units.

However, there would be the following options to meet the store order:

  • 1 box of 8 units and 1 box of 4 units (total: 12)

  • 1 box of 8 units and 2 boxes of 2 units (total: 12)

  • 1 box of 8 units and 1 box of 6 units (total: 14)

  • 1 box of 8 units, 1 box of 4 units and 1 box of 2 units (total: 14)

In a scenario like this I need an algorithm that might find the packaging combination to be closer to the exact value.

In the real scenario, there are dozens of possible combinations, where I need to find 3 possible combinations:

  • The combination that meets the exact requested quantity (requested: 20, combination: 20)
  • The combination that gets as close as possible through a lower value than requested (requested: 20, closest combination: 18)
  • The combination that answers as close as possible through a value greater than requested (requested: 20, closest combination: 23)

Is there an algorithm already known that can fit well into this scenario where I can just adapt to my context?

Improve this question
$\endgroup$
3
  • $\begingroup$ What is the question here? Can you not just preprocess the packaging to find total units then binary search? What have you tried? What are you stuck on? $\endgroup$ Commented Aug 20, 2017 at 1:37
  • $\begingroup$ Excuse me @ryan, I could not think of a clearer way than an example scenario. I have edited the question to try to make it clearer. $\endgroup$ Commented Aug 20, 2017 at 2:03
  • 4
    $\begingroup$ en.wikipedia.org/wiki/Subset_sum_problem $\endgroup$ Commented Aug 20, 2017 at 6:51

1 Answer 1

Reset to default
1
$\begingroup$

This is a common problem so there certainly exist many approaches to solve it. Below I'll sketch such an approach. It probably has a name but I don't know it:

The approach essentially sets up an array of target order sizes with an array length of actual order size + largest available package size. In each array element we store the ID of the package that can be used to increase the overall combined package size from a known solution for some smaller order size to get to the order size related to the index of the array. When we filled up the array we can go back from a realizable solution to an order size of 0 by collecting all the packages that lead to the respective solution. So this will be some kind of a dynamic programming approach.

We start at an order size of 0, go through all available packages and set the array index given by the respective package size to the ID of the package. Now we repeatedly increase the order size by 1 up to the target order size and for each order size we do the following:

If there is an ID of a package in the respective array element we again go through all available packages and store their ID in the array element "order size + package size" if that array element does not yet contain an ID. Otherwise we do nothing and just go on.

When we filled up the array in this way we can search in the neighborhood of the target order size for the array element that best fulfills our needs and also contains a package ID. From there we add the stored package ID to our solution and go back in the array by the size of that package. We do this repeatedly until we are back at a test order size of 0.

Of course, the solution we obtained in this way is not necessarily unique. We can prioritize certain packages by the order in which we process them when filling up the array.

Improve this answer
$\endgroup$
2
  • 3
    $\begingroup$ en.wikipedia.org/wiki/… $\endgroup$ Commented Aug 20, 2017 at 6:51
  • 2
    $\begingroup$ Thanks for the Link! It looks like there is an even more efficient approach by Koiliaris and Xu if I read this correctly. The paper on arxiv: arxiv.org/abs/1507.02318 $\endgroup$ Commented Aug 20, 2017 at 9:26

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.