简单背包问题-题解
Acoipp
·
·
题解
题面
简单背包问题-题面
推论
让 f(k,s) 表示选 k 个珠宝，总重量恰好为 s 时，总价值最大是多少。我们需要计算 f(k,s)（以下 n 均表示物品种数）。
推论1：
f(2k,s)=\max_{|i|\le\lfloor n/2\rfloor}f(k,\lfloor s/2 \rfloor -i)+f(k,\lceil s/2 \rceil +i)
推论2：
f(2k+1,s)=\max_{1\le i \le n} a_i + f(2k,s-i)
证明
第二个推论很显然，根据题目意思便可得到。
关于第一个推论，很容易看出左手边大于等于右手边。因此，我们着重于展现另一个不等式。
让 i_1,i_2,\cdots,i_{2k} 作为选物品的一个序列满足 \sum_{j=1}^{2k} i_j=s 且 \sum_{j=1}^{2k} a_{i_j}=f(2k,s)。
又设 J \subseteq \{1,2,\cdots,2k\} 满足 |J|=k 而且 \sum_{j\in J}i_j-s/2 取到最小值。
在不丧失一般性的情况下，我们可以假设 \sum_{j\in J}i_j \le s/2。
矛盾的是，假设 \sum_{j\in J}i_j < s/2-n/2。
因此，由于 \sum_{j\in J}i_j < \sum_{j\notin J}i_j，有 j\in J 和 j' \notin J 使得 i_j < i_{j'}。让我们考虑 J':=J \cup \{j'\} \backslash \{j\}。
又因为 0 \le i_{j'} -i_j \le n，我们有 \sum_{j\in J}i_j < \sum_{j\in J'}i_j < \sum_{j\in J}i_j+n < \frac{s}{2}+\frac{n}{2}。
这后一连串的不等式意味着 |\sum_{j\in J'}i_j-s/2|<|\sum_{j\in J}i_j-s/2| 是个矛盾的问题。因此，我们推导出 \frac{s}{2}-\frac{n}{2} \le \sum_{j\in J} i_j \le \frac{s}{2}。
以 s':=\sum_{j\in J}i_j，我们有 f(2k,s)=\sum_{j=1}^{2k}a_{i_j}=\sum_{j\in J} a_{i_j}+\sum_{j\notin J} a_{i_j} \le f(k,s')+f(k,s-s') \le \max_{0\le i \le \lfloor n/2 \rfloor}f(k,\lfloor s/2 \rfloor -i)+f(k,\lceil s/2 \rceil +i)。
时间复杂度
利用该推论，我们可以用动态规划算法来解决这个问题。初始状态是 (k, s)，转移需要 O(n) 的时间。剩下的就是转移时的约束所访问的状态的数量。
为了计算状态 \{k\}\times[l, r] 的答案，
- 如果k是奇数，我们必须访问 \{k-1\}\times[l-n,r-1]。
- 如果k是偶数，我们必须访问 \{k/2\}\times[\lfloor l/2\rfloor-\lfloor n/2\rfloor,\lceil r/2\rceil+\lfloor n/2 \rfloor]。
让 \{k\}\times [l,r] 为给定的 k 所访问的状态集；根据上面的观察，我们可以得出如下结果：当 k 为奇数时，r-l+1 \le 3n；当 k 为偶数时，r-l+1 \le 4n。
在任何情况下，对于给定的 k，访问的状态数量是 O(n) 级别的。此外，我们访问的 k 的总数是 O(\log K) 级别的。
因此，状态的总数是 O(n\log K)。
因此，这个算法的复杂度是 O(n^2\log K)。
这个算法可以通过循环或递归两种方式来实现，但是循环实现要快得多（程序运行时缓存命中的原因）。如果用不同的实现方式，递归版本可能会在某些 OJ 上超过时间限制。