CFgym103446I

若⼲物品具有体积 t_i 和价值 v_i，选出⾄多 k 件物品 将其体积翻倍，然后选出若⼲物品并将其分为体积和相同的两堆，问选出的物品价值之和最⼤是多少。

n \leq 100

周正：“这个题的状态定义是很经典的大家一定要记下来。”

我们首先定义一个暴力 DP ，设 f_{i,s_1,s_2,k} 表示第 i 个物品，第一个集合里分到体积为 s_1，第二个集合里分到体积为 s_2，已经翻倍了 k 个物品的值，但是这样状态数达到了 10^8 级别无法接受。

观察到这种两个东西相等的约束条件，实际上我们只关心他们的相对的差。不妨设 f_{i,d,k} 表示第 i 个物品，第一个集合里体积比第二个集合东西多了 d ，已经翻倍了 k 个物品的值。那么这样状态数就压下来了，接下来就考虑怎么 DP。

这个 DP 还是相对简单的背包，选⼊集合 1 的物品体积视为正，选⼊集合 2 的体积视为负，那么就有

f_{i,d,k} = \min \{ f_{i-1,d,k}, f_{i-1,d-v_i,k} +d_i, f_{i-1,d+v_i,k} +d_i, f_{i-1,d-2*v_i,k-1} +d_i, f_{i-1,d+2*v_i,k-1} +d_i, \}

第一维可以滚掉，时间复杂度 O(n^3 \times \max t)，记得 d 那一维可能有负数，全部加上 100 即可。

Code