问题描述:

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 :)

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.)