假设我们要从地点$ A $步行到地点$ B $，但是它们之间有几条河。为了从地方$ A $步行到地方$ B $，我们需要为每条河建造一座桥梁。
我们有几种类型的木板。不同类型的木板具有不同的成本和长度，但是相同类型的木板具有相同的成本和长度。我们可以用木板建造桥梁。但是，可用木板的数量是有限的。我们的目标是为每条河建造一座桥梁，同时将木板的总成本降至最低。
为了更好地描述问题，我们绘制了一个图来描述我们的问题。
在三条河中，所需桥梁的长度分别为$ d_1 $，$ d_2 $和$ d_3 $。
我们有$ 4 $类型的木板。令$ l_i $和$ c_i $表示第i种木板的长度和成本。令$ \ delta_i $表示第$ i $ th种木板的可用数量。令$ n_ {ij} $表示用于建造桥梁$ j $的木板数。
那么问题可以表述为：
最小化
$ \ sum_ {j = 1} ^ 3 \ sum_ {i = 1} ^ 4 n_ {ij} c_i $
s.t.
$ \ sum_ {i = 1} ^ 4 n_ {ij} l_i \ geq d_j $
$ \ sum_ {j = 1} ^ 3 n_ {ij} \ leq \ delta_i $
$ n_ {ij} \ geq 0 $和$ n_ {ij} \ in Z $
我认为这个问题应该是NP-Hard，因为它是整数编程问题。这是真的？有谁知道如何解决这个问题？甚至不是最佳解决方案。
最佳答案
如果您可以划分木板，并在多个桥上使用这些木板，并且可以在一个桥上使用不同类型的木板，则它不是NP完整的，因为您首先只使用每米最便宜的木板然后继续。
否则，它可能是NP完整的，因为它也是垃圾箱包装问题。
例如，如果您不能分割木板以在多个桥梁上使用碎片，则假设您具有以下数据集：
河1的差距为7米
河2的差距为6米
用木板：
10块7米长的木板。价格：每板60美元。每米8.57美元。
10块木板，每块6米。价格：每板40美元。每米6.66 $。
最便宜的选择是，以每块100美元的价格购买1块木板，而不是以总价120美元的价格购买3块最便宜的木板。
作为解决方案：查看元启发法（Tabu搜索，模拟退火，后期验收）和诸如OptaPlanner（java，开源）之类的软件。