问是否有一个众所周知的算法来分配木板给卡车？

EN

我必须实现下面描述的算法，我有两个问题：

• 这个问题NP-完全吗？
• 它类似于一个众所周知的算法问题吗？

问题

我有三个长度的木板:10米、8米和5米。

我需要把这些从一个地方运到另一个地方。

我有三种类型的卡车，A型，B型和C型。

每辆卡车最多可运载10块木板，而A型卡车则能运载各种木板，B型卡车只能运载8米和5米的木板，C型卡车只能运载5米的木板。

每辆卡车都有自己的运输木板的价目表：

Truck A
1 plank $50 
2-5 planks $100
6-10 planks $150

Truck B
1 plank $30
2-5 planks $90
6-10 planks $140

Truck C
1 plank $20
2-5 planks $80
6-10 planks $110

算法的目标是:找出最便宜的方法来运输一定集合的木板。

例子:我有5块10米的木板，1块8米的木板。

有两种可能的发行版本：

1. A型卡车6辆:150美元
2. A卡车5辆，B卡车1辆:100美元+30美元。

所以备选方案2是最好的。当我开始为更多的木板解决这个问题时，可能的组合的数量将会增加。

具体的价目表是可以改变的，但它永远不会节省钱，把同样大小的木板分给更多的卡车。

所以:如果我有20个相同大小的木板，解决办法总是:两辆卡车，每10块木板。我不需要尝试3辆或更多卡车的组合。

如果我有21块相同大小的木板，我只需要尝试所有涉及3辆卡车的组合。