1

I was asked to help make a basic materials calculator for a friend, but I'm not really sure what kind of algorithm this is since I only do some coding casually and my math skills are probably nowhere near as good as some of the people on here :) Here's the problem I am faced with...

I have multiple boxes(A) that each contain a certain subset of materials (B). These materials (B) are used to build items (C). Once the materials (B) are removed from the boxes (A) they must be used or thrown away. The requirements for the items (C) being built can sometimes change as this algorithm must cover multiple items.

Boxes (A) always have the same subset of materials (B) and this never changes.

Example: Boxtype 1 contains (32 mat1, 30 mat2, 24 mat3, 0 mat4) Boxtype 2 contains (1 mat1, 22 mat2, 13 mat3, 55 mat4) Boxtype 3 contains (55 mat1, 21 mat2, 1 mat3, 7 mat4)

I need to build item foo5 - It needs 4,311 mat1, 700 mat2, 443 mat3, 321 mat4. How many Boxes (A) are needed to do this with the least amount of waste.

I've tried searching around but without knowing what kind of algorithm it is I'm not having much luck on my searches.

Edit: To answer some questions also appending my reply to this post. Yes you can pick multiples of each box. Everything left over after the order is finished is thrown away. The boxes with the materials have a cost so optimizing at that level would be great if possible but is a secondary objective. Sorry if this was not clear as I am a bit new to this part :)

Peons
  • 13
  • 3
  • I am assuming you can pick multiples of each box, meaning 10x box1, 20x box 2, etc.? – Lasse V. Karlsen Jan 05 '17 at 06:57
  • What if you only use half of the materials from the last of box 1, what do you do with the rest? waste? – Lasse V. Karlsen Jan 05 '17 at 06:58
  • It is not clear what the objective to optimize should be. Do the boxes cause some cost? If not, just take as much material as you like and discard what you don't need, as it's for free. – Codor Jan 05 '17 at 07:09
  • Is the objective to minimize the number of selected boxes? – Codor Jan 05 '17 at 07:34
  • 1
    He said "least amount of waste", if "when you take one box, you use what you need and throw away the rest" then I assume it means minimize the leftover materials after building the item. But again, this kind of thing need to be explicitly specified in the question. – Lasse V. Karlsen Jan 05 '17 at 08:54
  • Yes you can pick multiples of each box. Everything left over after the order is finished is thrown away. The boxes with the materials have a cost so optimizing at that level would be great if possible but is a secondary objective. Sorry if this was not clear as I am a bit new to this part :) – Peons Jan 05 '17 at 11:41
  • 1
    This sounds like the knapsack problem, but instead of optimising value you minimise the waste... Also has the feel of a dynamic programming problem. – BeyelerStudios Jan 05 '17 at 11:50
  • My friends had similar problem as the interview task. Solded using simple greedy approach. There is not special algoritm for that – Anton Jan 05 '17 at 12:33

1 Answers1

0

Integer programming. Write code to construct an integer program like

Minimize
 waste1 + waste2 + waste3 + waste4
Subject To
 32 box1 +  1 box2 + 55 box3 - waste1 = 4311
 30 box1 + 22 box2 + 21 box3 - waste2 =  700
 24 box1 + 13 box2 +  1 box3 - waste3 =  443
  0 box1 + 55 box2 +  7 box3 - waste4 =  321
Bounds
  0 <= box1
  0 <= box2
  0 <= box3
  0 <= waste1
  0 <= waste2
  0 <= waste3
  0 <= waste4
Integer
  box1 box2 box3
End

and then feed it to your favorite integer program solver. (The program above is in CPLEX format.)

Community
  • 1
  • 1
David Eisenstat
  • 64,237
  • 7
  • 60
  • 120
  • Thank you very much this helps put me on the proper research path. :) Probably outside the realm of my usual casual coding but I will probably give it a hack anyway for the fun. – Peons Jan 06 '17 at 00:28