0/1背包问题、完全背包问题的扩展研究

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

以完全背包为例，方程：。

状态数组降维（空间复杂度优化）

• 从上面的式子可以看出,总是被算出来的，因此就可以降维了；
  方程：。

n比较小的时候

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

最大价值比较小（时空复杂度优化）

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

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

• 用公约数压缩——Shk3。