贪心加暴力
大范围贪心，小范围暴力
这一类做法，通常不是很好想，但是很多题目都能这样做。
例题
有一个超级大的背包，物品的价值等于容量，但是物品只有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
这样的做法就已经很快了。