大范围贪心，小范围暴力

这一类做法，通常不是很好想，但是很多题目都能这样做。

例题

有一个超级大的背包，物品的价值等于容量，但是物品只有8种容量分别为1-8 给你每个物品的数量ai，和背包总容量w，问能背走的最大价值是多少 w<1e18;

朴素背包

设dp[i][j]为前i类物品，背满j是否可行,复杂度$O(8\times n)$

复杂度为什么这么大？

状态过多，状态冗余，可能存在某些能合并的状态

分解背包

​ 840是1-8的数的lcm, 于是我们可以把背包W分为 $840k + (W-840k)$ 两个部分。 且后一部分小于$840\times8$

为什么要这么分?

先谈谈唯一分解

我们对每一种放法 ，进行唯一分解:

先把每一类容量相等的物品唯一分解为两部分, 第一部分的总容量为840的一个倍数，第二部分总容量小于840

比方说某种方法选择了1000个1，3000个2，5000个3…

那么我们将其唯一分解为:

$1\times840+160个1$

$7\times 420+ 60个2$

$17\times280+240个3$
然后把每类容量为840的倍数的那一部分合在一起:
于是成了$(1\times840+7\times420\times2+17\times280\times3) + 160\times1+60\times2+240\times3+0\times4+0\times5+…$
=$840\times25 + 160\times1+60\times2+240\times3+0\times4+0\times5+…$ 这就是唯一分解。

根据唯一分解优化dp

然后我们考虑，为什么这一题不能使用，背包，因为容量大？物品多？是的，

但是这些都只是表面上的。我们深入思考，能不能把某些没有意义的方案合并到一个状态里面呢？

我们不要设dp[i][j]表示什么前i类物品装满容量j是否可行这样的状态。因为这是$8\times n$级别的状态
我们根据唯一分解，设dp[k][i][j]代表背包的第一个部分容量为840*k,第二部分为前i类物品装满容量j
若值为1，代表可行，否则不可行。

状态的个数

显然k<n/840,i<8, j<840*8

现在的状态数为(n/840)*8*(840*8)

状态数目变多了。转移也更加复杂，看似此状态还不如朴素做法。

单调性

这一点应该是很容易想到的。这个dp[k][i][j],具有单调性，一定存在某个值t, 使得dp[k][i][j]的值在i和j固定，k<=t的时候全为1，在k>t的时候全为0

显然这个t是最优的

优化

我们换一种状态的设法，设dp[i][j]为只取前i类物品的方案的唯一分解下，不考虑背包容量上限，第二部分容量为j，第一部分的k能取到的大值。

转移方程

dp[i][j] —> dp[i+1][j+t*i] t是选取的数量，j+t*i<8*840

这样的做法就已经很快了。