algorithm - 是否有一种众所周知的算法来为卡车分配木板？

Question

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

• 这个问题是 NP 完全的吗？
• 是否与知名品牌相似算法问题？

问题

我有三种长度的木板:10m、8m 和 5m。

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

我可以使用三种类型的卡车，卡车 A、卡车 B 和卡车 C。

每辆卡车最多可以装10 block 木板，但是A车可以装所有类型的木板，B车只能装8m和5m的木板，C车只能装5m的木板。

每辆卡车都有自己的运输木板价格表:

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 block 10m 的木板和 1 block 8m 的木板。

有两种可能的分布:

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

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

具体的价目表可能会发生变化，但将相同尺寸的木板分配给需要的更多卡车永远不会省钱，这一点始终是正确的。

所以:如果我有 20 block 相同尺寸的木板，解决方案总是:2 辆卡车，每 10 block 木板。我不需要尝试 3 辆或更多卡车的组合。

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

Answer 1

这个问题是装箱问题的推广，这使得它成为一个 NP-hard 问题。请引用此链接:http://en.wikipedia.org/wiki/Bin_packing_problem