AT_dp_e Knapsack 2 分析

· · 个人记录

本题的特点是 W 极大，而 v_i 与 N 却较小。求的是在总重量小于等于 W 的前提下的最大价值。

我们可以进行一个简单的思维转换：将问题转换为价格最大时的最小重量。也即，将价格作为状态，求出价格为某时的最小体积。

之后我们自后往前遍历 dp 数组并找到第一个满足 dp[i] <= w 的 i。此时 i 就是最大的价格。

归纳边界：dp[0] = 0