nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial

大范围贪心,小范围暴力

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

例题

有一个超级大的背包,物品的价值等于容量,但是物品只有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

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