02/05

近日在做USACO的水题PROB Score Inflation,这道题是一个完全背包加上一个将绝对没用的(\(\mathbf{for}\; j\in \mathbb {T},\exists k \in \mathbb {T}, s_j\le s_k \; \mathbf{and}\; p_j\ge p_k\))的\(j\)去掉的剪枝。不过我做完这道题了以后,偶然间想到了体积很大的情况,经过与网友的讨论初步得出了解决办法。(为了表述方便,一下V代表体积、N代表物品数目)

以完全背包为例,方程:\(f_{i,j}=\max \left \{f_{i-1,j},f_{i,j-w_i} \right \}\)

状态数组降维(空间复杂度优化)

  • 从上面的式子可以看出,\(f_{i,j-w_i}\)总是被算出来的,因此就可以降维了;
    方程:\(\mathbf{for}\;i\in \left [1,n \right ], f_{j}=\max \left \{f_{j},f_{j-w_i} \right \}\)

n比较小的时候

  • 状态压缩动态规划(时空复杂度优化)——代谢终产物/bb(35869****);
  • \(n\le20\) 时,搜索出所有体积(时空复杂度优化)——Gardenia(16816****);
  • 深度/广度优先搜索(空间复杂度优化)——孤柏(3767****)。

最大价值比较小(时空复杂度优化)

  • 用价值当状态——代谢终产物/bb(35869****)。

每个物品的体积较大(时空复杂度优化)

  • 用公约数压缩——Shk3。