假设我们想从$A$ 走到$B$，但是它们之间有几条河流。为了从$A$ 走到$B$，我们需要为每条河流建造一座桥。
我们有几种类型的木板。不同类型的木板成本和长度不同，但相同类型的木板成本和长度相同。我们可以用木板搭桥。但是，可用木板的数量是有限的。我们的目标是为每条河流建造一座桥梁，同时最大限度地降低木板的总成本。
为了更好地描述问题，我们画了一个图来描述我们的问题。
有 3 条河流需要的桥梁长度分别为 $d_1$、$d_2$ 和 $d_3$。
我们有 4 美元的木板。令 $l_i$ 和 $c_i$ 表示第 $i$ 种木板的长度和成本。令$\delta_i$ 表示第$i$ 种木板的可用数量。令 $n_{ij}$ 表示用于建造桥梁 $j$ 的木板数量。
那么问题可以表述如下：
最小化 $\sum_{j=1}^3 \sum_{i=1}^4 n_{ij}c_i$
英石
$\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，因为它是一个整数规划问题。这是真的？有谁知道如何解决这个问题？即使是不是最优的解决方案。