Suppose we want to walk from place $A$ to place $B$, but there are several rivers between them. In order to walk from place $A$ to place $B$, we need to build a bridge for each river.
We have several types of planks. Different types of planks have different costs and lengths, but the same type of planks have the same cost and length. We can use planks to build bridges. However, the number of available planks are limited. Our objective is to build a bridge for each river while minimizing the total cost of planks.
To better describe the problem, we draw a figure to describe our problem.
There are three rivers where the length of bridges needed are $d_1$, $d_2$, and $d_3$, respectively.
We have $4$ types of planks. Let $l_i$ and $c_i$ denote the length and cost of the $i$th type of plank. Let $\delta_i$ denote the available number of $i$th type of planks. Let $n_{ij}$ denote the number of planks used for build bridge $j$.
Then the problem can be formulated as follows:
Minimize $\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$
I think this problem should be NP-Hard as it is an integer programming problem. Is this true? Does anyone know how to solve this problem? Even a solution which is not optimal.
If you can divide planks, and use the pieces on multiple bridges, and you can use planks of different types on a single bridge, it's not NP-complete because you just use the cheapest plank per meter first and continue on.
Otherwise it is probably NP-complete, because it's a bin packing problem too. For example, if you can't divide planks to use the pieces on multiple bridges, suppose you have this dataset:
With planks:
The cheapest option is to buy 1 plank of each for a total of 100$, not to buy 3 planks of the cheapest kind for a total of 120$.
As for a solution: look in to metaheuristics (Tabu Search, Simulated Annealing, Late Acceptance) and software such as OptaPlanner (java, open source).