3

A manufacturer sells different flavour chocolates.

Customers can place an order for any number of each flavour chocolate, from zero upwards.

Some combinations of chocolates are frequently ordered, so the manufacture has prepackaged these combinations in his warehouse to make dispatch quicker (which saves money). There's no restriction on how many chocolates can be pre-packed in to a box e.g

box 1 = 3 x Strawberry, 3 x Coffee, 1 x Orange;

box 2 = 1 x Strawberry, 3 x Coffee, 5 x Lime

How would we determine if the customer's order can be (fully or partially) fulfilled using a combination of prepackaged chocolates and how many of each box are required ?

(Although this sounds like it's not a real world problem, it is the simplest analogy that I could come up with for my real world problem that doesn't require an understanding of the specific industry & conditions that the real problem relates to)

  • Hey, if you're going to bother to mark the question down, then please at least give some pointers as to why or how to improve it. – David Rose Feb 3 at 10:53
  • Welcome! This seems not to be a real manufacturing problem: if the manufacturer produces boxes, the customers order boxes. Since it appears to be an exercise, you should not start with wild guesses: what does make your first half think it is knapsack? And what does make your second half doubt? – Christophe Feb 3 at 10:54
  • P.S: I did not DV (yet), but I guess people dv because of the impression of lack of research. – Christophe Feb 3 at 10:57
  • I'd just ask for a solution rather than asking if this is knapsack or not... try to ask a single question too to increase your chance to get useful responses. – Martin K Feb 3 at 14:38
  • @MartinK thanks. Question now edited. – David Rose Feb 4 at 10:28
1

It is a knapsack problem:

Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.

Source: https://en.wikipedia.org/wiki/Knapsack_problem

The value of each box is the amount of money it saves you to ship that box compared to packing its content as individual box. Some boxes will save you more than other boxes, however, trying to first pick the box that saves you the most is not always the optimal solution as by choosing this box, you make it impossible to choose other boxes and these other boxes together could have saved you even more money in the end.

Yet if the only intention of those boxes is saving money, keep in mind that any expensive computation wastes money as you either need to rent more computation time or invest into more powerful equipment and/or consume more electric power; either way you will have more expenses. Sure, the expenses may be small per order but you will have them for every order, even orders where no box matches are found in the end. Thus saving money with boxes won't work unless you can keep computation work small and boxes are chosen very well to really match what most customers will order.

The knapsack problem is not unsolvable, it just cannot be solved in polynomial time. The question is, will it really save you any money if you need to invest that much computation power to solve that problem? So the typical solution is to use a good approximation that won't find the optimal solution but that will find a good solution nonetheless. A simple solution is a greedy approach:

  1. For all boxes, calculate how much money it will save you if a customer orders that box instead of forcing you to pack the same items separately. Boxes with more items should save more money than boxes with less items (packing costs increase with the number of items), yet maybe even the content plays a role in case there are different packing cost for different chocolates (chocolate sizes, chocolate weights, chocolate storage locations, and so on).

  2. Sort that list by the calculated saving value, those with the highest savings are on top. The relative order of boxes that save the same amount of money is irrelevant.

  3. Process the list from top to bottom. For every box, see if you can subtract the items in the box from the customer order. If you can, do it and repeat with the same box (keep in mind, that the same box can be subtracted multiple times), if you cannot, continue with the next box on the list.

  4. If you hit the end of the list and there are still items left in the customer order, those need to be packed separately.

The complexity of this algorithm is O(n) where n is the number of boxes on the list. Please note that you only need to perform step 1 and step 2 once and not for every order. You only need to repeat them if the set of available boxes changes. Of course, that algorithm won't give you optimal results but if you have a reasonable set of boxes, it will give you good results with acceptable linear processing time.

You may also further optimize this algorithm by trading memory for processing speed: E.g. you can create a list with all chocolates and then various filtered lists like "All chocolates but strawberry", "All chocolates but coffee", and "All chocolates but strawberry and coffee". What's the advantage? Well, if a customer doesn't order any strawberry, then processing the all chocolate list isn't meaningful. Instead you just process the "All chocolates but strawberry" list, unless the customer also ordered no coffee. Finding the right list just requires a few quick tests in the beginning and if the filtered lists are much smaller than the all chocolate list, this optimization can really pay off. Of course, it doesn't make sense to create filtered lists for all possible combinations but if every second box contains strawberry and every second customer won't order any, then creating a no strawberry list is definitely worth the effort.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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