验题人题解 | 火星背包 II

Sol 1

不难发现，题意就是 $01$ 背包，用朴素的 $01$ 背包方式维护即可。

准确地说，用 dp 维护，设 $f_{i,w}$ 表示考虑前 $i$ 个物品，重量不超过 $w$ 的最大价值。

那么我们的决策其实只有第 $i$ 个物品选/不选。

• 选

  此时，重量会累计 $w_i$，价值会累计 $v_i$。

  考虑此时重量为 $w$，则选以前，重量是 $w-w_i$。

  所以 $f_{i,w}=f_{i-1,w-w_i}+v_i$。

• 不选

  此时的情况与 $f_{i-1,w}$ 一摸一样，即 $f_{i,w}=f_{i-1,w}$。

综上所述，dp 的状态转移方程就昭然若揭了，即

$$f_{i,w}=\max(f_{i-1,w},f_{i-1,w-w_i+v_i})$$

最后答案即为 $f_{n,m}$。

时间复杂度、空间复杂度均为 $O(nm)$。

期望得分 50 分

Sol 2

上面做法的瓶颈是 $m$ 大（本题 $m$ 可以达到 $10^9$）时时间复杂度就会变得不可接受。

我们惊奇的发现，$v_i$ 和 $w_i$ 的值域似乎很不同。

也就是说，就算所有东西都买上，总价值也只有 $\sum v_i \le 10^3\times 100 = 10^5$。

这时候可以想到 dp 的一种经典 trick，状态和目标函数转换。

也就是原来的方程 $f_{i,w}=v$，我们想成 $g_{i,v}=w$。

也就是，$g_{i,v}$ 表示前 $i$ 个物品，价值是 $v$ 的最小重量。

与前面的决策讨论类似，具体讨论过程留给读者自己思考。

$$g_{i,v}=\min(g_{i-1,v-v_i}+w_i,g_{i-1,v})$$

答案是最大的 $v$ 使得 $g_{n,v}\le m$。

时间复杂度 $O(nV)$，空间复杂度 $O(nV)$。此处 $V=\sum v_i$。

这时会 MLE。

我们发现 $g$ 的决策，只依赖于上一行。也就是往前的两行三行四行都没有用了，可以不再记录。

采用 滚动数组 的方式进行记录，空间复杂度降为 $O(V)$。

如果不会滚动数组可以借鉴代码或者自行百度。

void solve(){
	cin>>n>>m;
	for(ll i=1;i<=n;i++){
		cin>>w[i]>>v[i];
	}
	ll V=accumulate(v+1,v+1+n,0);
	ll ans=0;
	for(ll j=0;j<=V;j++) dp[0][j]=1e18;
	dp[0][0]=0;
	for(ll i=1;i<=n;i++){
		for(ll j=0;j<=V;j++) dp[i&1][j]=dp[i&1^1][j];
		for(ll j=v[i];j<=V;j++){
			dp[i&1][j]=min(dp[i&1^1][j-v[i]]+w[i],dp[i&1][j]);
			if(dp[i&1][j]<=m) ans=max(ans,j);
		}
	}
	cout<<ans<<endl;
}