洛谷P3613寄包柜vector求解

洛谷P3613题目链接：https://www.luogu.com.cn/problem/P3613

题目描述：

有 $n$ 个包裹要寄，第 $i$ 个包裹重量为 $w_i$，你需要选择若干个包裹放到两个体积为 $v$ 的快递柜中，使得两个柜子的重量差最小，输出这个最小的重量差。

$n ≤ 20, 1 ≤ v ≤ 250, 1 ≤ w_i ≤ 50$

思路分析：

这道题目可以使用动态规划来解决。

我们可以定义 $f_{i,j}$ 表示在前 $i$ 个物品中选若干个放入第一个体积为 $j$ 的快递柜中的最大价值。

那么我们可以得到状态转移方程为：

$$
f_{i,j}=\max\{f_{i-1,j-w_i}+w_i,f_{i-1,j}\}
$$

其中，当 $j<w_i$ 时，$f_{i,j}=f_{i-1,j}$。

同理，我们可以定义 $g_{i,j}$ 表示在前 $i$ 个物品中选若干个放入第二个体积为 $j$ 的快递柜中的最大价值，那么状态转移方程为：

$$
g_{i,j}=\max\{g_{i-1,j-w_i}+w_i,g_{i-1,j}\}
$$

其中，当 $j<w_i$ 时，$g_{i,j}=g_{i-1,j}$。

最后，我们可以枚举两个快递柜的重量之和 $s$，然后用 $ans=\min\{ans,|f_{n,v}-g_{n,s-v}|\}$ 来更新答案。

时间复杂度为 $O(2^n\times v)$，可以通过此题。另外，由于数据范围比较小，我们也可以使用状态压缩来优化。