本文涉及知识点

动态规划汇总
状态机dp

01背包

有n件物品，体积分别是v[i]，价值分别是w[i]，有个包的容积是bv。如何选择物品使得，在总体积不超过bv的前提下，让总价值最大。

动态规划的状态表示

dp[i][j] 表示处理完前i件物品，占用体积是j的最大价值。
如果不用滚动向量，空间复杂度是O(n$\times$bv)

动态规划的状态方程

如果选择选择标为i的物品：
MaxSelf(dp[i+1][jv[i]] ,dp[i][j]+w[i])
如果不选择下标为i的物品：
MaxSelf(dp[i+1][j],dp[i][j])
转移方程的时间复杂度为O(1)
故总时间复杂度为：O(n$\times$bv)

动态规划的初始状态

全为0。

动态规划的填表顺序

依次枚举各物品。

动态规划的返回值

dp.back()的最大值。

多重背包

多重背包：每件物品有多件n[i]。
暴力做法：每件物品都枚举0到n[i]。空间复杂度：O(bv $\times \sum n$)

完全背包

完全背包：每件物品无限。暴力做法，类似多重背包。

多重背包、完全背包通过二进制转化成01背包

完全背包：我们可以把物品拆分1 + 2 + 4+ 8 + $\cdots$ 这样时间复杂是O(n$\times$bv $\times$ logmax)
多重背包假定某个物品有x件：
拆分成：1+2+4+8 + $\cdots$ + y
y = x - (1 + 2+4+8 $\cdots$) ,y > 0，y尽可能得小 。
我们来证明，这样可以选择：[0,x]
令y前面有i 项： 则通过选或不选前i项，范围为：[0,2ⁱ)
y < 2ⁱ
如果选择y，则范围为：[y,y+2ⁱ)
两者结合就是：[0,y+2ⁱ)
y+2ⁱ-1就是x，故可以表示[0,x]

优化求最大价值的背包

都可以优化到时间复杂度：O(n$\times$bv)

完全背包

dp[i][j] = max(dp[i][j-v[i]]+w[i],dp[i-1][j])
分别对应两种情况：
一，选择物品i。只需要考虑选择一个，因为dp[i][j-v[i]] dp[i][j-v[i]*2] $\cdots$ 可能也选择了一个。
二，不选择物品i。

单调双向队列优化多重背包

for(int j1 = 0 ; j1 < v[i];j1++)
for(int j = j1; j <= bv; j+= j1 ){
$\cdots$
}
队列que中记录如下数据：{pre[j1],pre[j1v[i]]-w[i],pre[j1+([i]-v[i])*2 $\cdots$ }
max(que)+ ( j- j1)/v[i] *w[i] 就是dp[i][j]。
问题一：
( j- j1)/v[i] > n[i] ，就需要队首出队，直到 ( j- j1)/v[i] == n[i]。
问题二，如何求最大值：
前面的数据先出队，如果前面的数据小于等于后面的数据，则前面的数据被淘汰了。
数据淘汰后，队列的数据降序，也就是队首数据最大。

优化统计方案数

都可以优化到时间复杂度：O(n$\times$bv)

完全背包

dp[i][j] = dp[i][j-v[i]]+ dp[i-1][j] 分别对应两种情况：最有一件物品是i，最后一个物品不时i。从小到大选择物品。

同余前缀和优化

dp[i][j] = ∑ k 1 j d p [ i − 1 ] [ k ] \sum_{k1}^{j} dp[i-1][k] ∑k1j​dp[i−1][k] k1= max( j%[v[i]],j - v[i]*n[i])

分组背包

n组物品，每组有多件，价值和容量可能不同。每组只能选择0个或1个。求最大价值。类似多重背包的暴力解法。

例题(2024年11月2号整理)

题解	难度分
定界01背包
【C++动态规划 01背包】2915. 和为目标值的最长子序列的长度	1658
【C++动态规划 01背包】2787. 将一个数字表示成幂的和的方案数	1817
【C++动态规划 01背包】1049. 最后一块石头的重量 II	2092
【动态规划】879. 盈利计划	2204
完全背包
【动态规划】【C++算法】2188. 完成比赛的最少时间	2135
【动态规划】【数学】【C++算法】1449. 数位成本和为目标值的最大数字	1927
类似多重背包
【C++动态规划 多重背包】1774. 最接近目标价格的甜点成本	1701
【多重背包 动态规划】2585. 获得分数的方法数	1909
【动态规划】【同余前缀和】【多重背包】2902. 和带限制的子多重集合的数目	2758
分组背包
【C++动态规划 分组背包】1155. 掷骰子等于目标和的方法数	1653
【C++动态规划 分组背包】1981. 最小化目标值与所选元素的差	2009