背包问题 | wsztrush
背包问题是一类组合优化的NP问题：
给定一组物品，每个物品有一定的重量和价值，在一定的限制内，我们如何选择才能使总价值最高？
不同限制的解法也不相同。
0-1背包
问题描述：
有$N$种物品，重量为$weight[i]$、价值为$value[i]$，现有背包承重$total$，每种物品最多拿一个，怎样拿总价值最大？
假设每种物品的数量为$count[i]$，于是有：
$$
\begin{align}
\max \quad & \sum count[i] · value[i] \\
st \quad & \sum count[i] · weight[i] \leqslant total \\
& count[i] \in { 0, 1}
\end{align}
$$
当$total$不是很大的时候，打表$tab[i]$为重量为$i$时的最大价值，依次考虑物品$j$，有：
$$
tab[i+weight[j]] = max (tab[i+weight[j]], tab[i] + value[j])
$$
完全背包
问题描述：
有$N$种物品，重量为$weight[i]$、价值为$value[i]$，现有背包承重$total$，每种物品可以拿任意个，怎样拿总价值最大？
假设每种物品的数量为$count[i]$，于是有：
$$
\begin{align}
\max \quad & \sum count[i] · value[i] \\
st \quad & \sum count[i] · weight[i] \leqslant total \\
& count[i] \in N
\end{align}
$$
打表$tab[i]$为重量为$i$时的最大价值，依次考虑物品$j$放入$k$件的情况，有：
$$
tab[i+weight[j] · k] = max(tab[i+weight[j] · k], tab[i] + value[j] · k)
$$
多重背包
问题描述：
有$N$种物品，重量为$weight[i]$、价值为$value[i]$，现有背包承重$total$的背包，每种物品分别可以拿$count[i]$个，怎样拿总价值最大？
和完全背包的解法相同，仅仅是在超过物品数限制之后不再尝试即可。另一种解法是：
将物品$i$转换为重量为$2^0·weight[i],2^1·weight[i],…,2^{log(count[i])}·weight[i]$的不同商品。
于是多重背包可以转换为0-1背包处理（利用二进制的思想来加快速度还是很有意思的）。
二维背包
问题描述：
有$N$种物品，重量为$weight[i]$、体积为$volume[i]$、价值为$value[i]$，现有背包承重$totalWegiht$、体积为$totalVolume$，每种物品最多拿一个，怎样拿总价值最大？
假设每种物品的数量为$count[i]$，于是有：
$$
\begin{align}
\max \quad & \sum count[i] · value[i] \\
st \quad & \sum count[i] · weight[i] \leqslant totalWeight \\
& \sum count[i] · volume[i] \leqslant totalVolume \\
& count[i] \in { 0, 1}
\end{align}
$$
此时打个二维表$tab[i][j]$表示重量为$i$、体积为$j$时的最大价值，转移方程为：
$$
tab[i+weight[k]][j+volume[k]] = max (tab[i+weight[k]][j+volume[k]], tab[i][j] + value[k])
$$
多背包
问题描述：
有$N$种物品，重量为$weight[i]$、价值为$value[i]$，现有$M$背包分别承重$totalWegiht$，每种物品最多拿一个，怎样拿总价值最大？
现在没想到（也没找到）比较好的确定算法，大多思路为启发式搜索或者有一定策略的贪心。
