背包问题
0-1背包¶
描述：给定物品\(j=0,\cdots,m\)，重量\(w_j\)，价值\(c_j\)，对于容量为\(W\)的背包，求能容纳物品的最大价值（每个物品仅能使用一次）
0-1线性规划建模：设二进制变量\(x_j\in\{0,1\}\)对应是否选择物品\(j(j=0,\cdots,m)\)，添加负号，将最大化问题转化为最小化问题
\[
\begin{array}{rl}
\text{minimize}&-c_0x_0-c_1x_1-\cdots-c_mx_m\\ s.t.&w_0x_0+w_1x_1+\cdots+w_mx_m\leqslant W\\
&x_j\in\{0,1\},\quad j=0,\cdots,m
\end{array}
\]
多重背包¶
描述：给定物品\(j=0,\cdots,m\)，重量\(w_j\)，价值\(c_j\)，对于容量为\(W\)的背包，求能容纳物品的最大价值（每个物品能使用多次）
整数线性规划建模：设变量\(a_j\in \mathbb{N}\)为选择物品\(j\)的数量
\[
\begin{array}{rl}
\text{minimize}&-c_0a_0-c_1a_1-\cdots-c_ma_m\\ s.t.&w_0a_0+w_1a_1+\cdots+w_ma_m\leqslant W\\
&a_j\in\mathbb{N},\quad j=0,\cdots,m
\end{array}
\]