第三题 - 火星背包 II 题目链接跳转：点击跳转 一道反向 0/10/10/1 背包的模板题目。通常，0/10/10/1 背包问题的目标是选择若干物品，使得这些物品的总重量不超过背包容量，并且这些物品的总价值最大化。而反向 0/10/10/1 背包问题则是反其道而行之，其目标是选择若干物品，使得这些物品的总重量不低于给定的最小值，并且这些物品的总价值最小化。 主要就是状态的定义比较难：设 dp[j]dp[j]dp[j] 表示恰好凑出总重量为 jjj 的最小代价。那么我们可以得到如下的状态转移方程： dpj=min⁡(dpj,dpj−wi+vi);dp_j = \min(dp_j, dp_{j-w_i} + v_i); dpj =min(dpj ,dpj−wi +vi ); 根据状态的定义，我们将 dpdpdp 数组一开始全部初始化为正无穷大，同时另 dp0=0dp_0 = 0dp0 =0，表示恰好凑出重量为 000 的物品的最小代价为 000，正无穷大代表暂时还没有答案，需要在后续的循环中更新。 之后就是跑一遍正常的 Knapsack 01 代码就好了。在输出答案的时候，我们需要找到一个满足条件 (dp[i]≤m)(dp[i] \le m)(dp[i]≤m) 的最大值。用一个 for 循环就可以搞定了。 本题的 AC 代码如下：

题目解析 本道题目不难想到套用经典的「01背包问题」，定义 dp[i][j]\tt{dp[i][j]}dp[i][j] 为前 iii 个物品，背包容量为 jjj 可以获取的最大价值，然后使用 dp[i][j]=max⁡(dp[i−1][j],dp[i−1][j−w[i]]+v[i])\tt{dp[i][j] = \max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i])}dp[i][j]=max(dp[i−1][j],dp[i−1][j−w[i]]+v[i]) 进行转移。 此种做法只能够拿到一部分分数（约 40%40\%40%），无法通过本题，原因是本题背包的容量和物品的重量都特别大 (1≤wi≤M≤109)(1 \le w_i \le M \le 10^9)(1≤wi ≤M≤109)。使用上述方式解决这道题目的时间复杂度为 O(NM)\mathrm{O}(NM)O(NM)。 但本题 NNN 以及 viv_ivi 的值都比较小，我们不妨将定义更改为 dp[i][j]\tt{dp[i][j]}dp[i][j] 为前 iii 个物品获取价值为 jjj 所需要的最小重量，然后使用 dp[i][j]=min⁡(dp[i−1][j],dp[i−1][j−v[i]]+w[i])\tt{dp[i][j] = \min(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i])}dp[i][j]=min(dp[i−1][j],dp[i−1][j−v[i]]+w[i]) 进行转移。由于 j≤∑i=1Nvij \le \sum_{i=1}^{N}v_ij≤∑i=1N vi ，此方法的复杂度为 O(N×∑i=1Nvi)\mathrm{O}(N \times \sum_{i=1}^{N}v_i)O(N×∑i=1N vi )，在本题的数据范围下完全可以通过。 AC代码

SOL 1 不难发现，题意就是 010101 背包，用朴素的 010101 背包方式维护即可。 准确地说，用 dp 维护，设 fi,wf_{i,w}fi,w 表示考虑前 iii 个物品，重量不超过 www 的最大价值。 那么我们的决策其实只有第 iii 个物品选/不选。 * 选 此时，重量会累计 wiw_iwi ，价值会累计 viv_ivi 。 考虑此时重量为 www，则选以前，重量是 w−wiw-w_iw−wi 。 所以 fi,w=fi−1,w−wi+vif_{i,w}=f_{i-1,w-w_i}+v_ifi,w =fi−1,w−wi +vi 。 * 不选 此时的情况与 fi−1,wf_{i-1,w}fi−1,w 一摸一样，即 fi,w=fi−1,wf_{i,w}=f_{i-1,w}fi,w =fi−1,w 。 综上所述，dp 的状态转移方程就昭然若揭了，即 fi,w=max⁡(fi−1,w,fi−1,w−wi+vi)f_{i,w}=\max(f_{i-1,w},f_{i-1,w-w_i+v_i}) fi,w =max(fi−1,w ,fi−1,w−wi +vi ) 最后答案即为 fn,mf_{n,m}fn,m 。 时间复杂度、空间复杂度均为 O(nm)O(nm)O(nm)。 期望得分 50 分 SOL 2 上面做法的瓶颈是 mmm 大（本题 mmm 可以达到 10910^9109）时时间复杂度就会变得不可接受。 我们惊奇的发现，viv_ivi 和 wiw_iwi 的值域似乎很不同。 也就是说，就算所有东西都买上，总价值也只有 ∑vi≤103×100=105\sum v_i \le 10^3\times 100 = 10^5∑vi ≤103×100=105。 这时候可以想到 dp 的一种经典 trick，状态和目标函数转换。 也就是原来的方程 fi,w=vf_{i,w}=vfi,w =v，我们想成 gi,v=wg_{i,v}=wgi,v =w。 也就是，gi,vg_{i,v}gi,v 表示前 iii 个物品，价值是 vvv 的最小重量。 与前面的决策讨论类似，具体讨论过程留给读者自己思考。 gi,v=min⁡(gi−1,v−vi+wi,gi−1,v)g_{i,v}=\min(g_{i-1,v-v_i}+w_i,g_{i-1,v}) gi,v =min(gi−1,v−vi +wi ,gi−1,v ) 答案是最大的 vvv 使得 gn,v≤mg_{n,v}\le mgn,v ≤m。 时间复杂度 O(nV)O(nV)O(nV)，空间复杂度 O(nV)O(nV)O(nV)。此处 V=∑viV=\sum v_iV=∑vi 。 这时会 MLE。 我们发现 ggg 的决策，只依赖于上一行。也就是往前的两行三行四行都没有用了，可以不再记录。 采用 滚动数组 的方式进行记录，空间复杂度降为 O(V)O(V)O(V)。 如果不会滚动数组可以借鉴代码或者自行百度。