背包问题汇总

本文涉及知识点

动态规划汇总

状态机dp

01背包

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

动态规划的状态表示

dp[i][j] 表示处理完前i件物品，占用体积是j的最大价值。

如果不用滚动向量，空间复杂度是O(n× \times×bv)

动态规划的状态方程

如果选择选择标为i的物品：

MaxSelf(dp[i+1][j+v[i]] ,dp[i][j]+w[i])

如果不选择下标为i的物品：

MaxSelf(dp[i+1][j],dp[i][j])

转移方程的时间复杂度为O(1)

故总时间复杂度为：O(n×bv)

动态规划的初始状态

全为0。

动态规划的填表顺序

依次枚举各物品。

动态规划的返回值

dp.back()的最大值。

多重背包、完全背包转化成01背包

多重背包：每件物品有多件n[i]。

完全背包：每件物品无限。

完全背包：我们可以把物品拆分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]

完全背包

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。

时间复杂度为：O(n× \times×bv)

单调双向队列及多重背包

for(int j1 = 0 ; j1 < v[i];j1++)

for(int j = j1; j <= bv; j+= j1 ){

⋯ \cdots⋯

}

队列que中记录如下数据：{pre[j1],pre[j1+v[i]]-w[i],pre[j1+(v[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]。

问题二，如何求最大值：

前面的数据先出队，如果前面的数据小于等于后面的数据，则前面的数据被淘汰了。

数据淘汰后，队列的数据降序，也就是队首数据最大。

例题

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。

https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程

https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版

https://download.csdn.net/download/he_zhidan/88348653

测试环境

操作系统：win7 开发环境： VS2019 C++17

或者 操作系统：win10 开发环境： VS2022 C++17

如无特殊说明，本算法用**C++**实现。