当前位置: 动力学知识库 > 问答 > 编程问答 >

What kind of algorithm is needed for this

问题描述:

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

分享给朋友:
您可能感兴趣的文章:
随机阅读: