02/05

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

以完全背包为例,方程:\(\)

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

  • 从上面的式子可以看出,\(\)总是被算出来的,因此就可以降维了;
    方程:\(\)

n比较小的时候

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

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

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

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

  • 用公约数压缩——Shk3。