背包问题
2021/7/1 6:22:14
本文主要是介绍背包问题,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
背包(资源型DP)
01背包
01背包(ZeroOnePack): 有N件物品和一个容量为V的背包。(每种物品均只有一件)第i件物品的费用是c[i]
,价值是w[i]
。求解将哪些物品装入背包可使价值总和最大。
这是最基础的背包问题,特点是:每种物品仅有一件,可以选择放或不放。
用dp[i][v]
表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。
状态转移方程
dp[i][v] = max(dp[i-1][v],dp[i-1][v-c[i]]+w[i])
状态转移方程的理解:
当把第i件物品放进容量v的背包时,前i-1件物品的状态已经确定,这时有两种情况
- 第i件物品不放进去,这时所得价值为:
dp[i-1][v]
- 第i件物品放进去,这时所得价值为:
dp[i-1][v-c[i]]+w[i]
最后比较两种情况的价值大小,dp[i][v]
是其中较大的。
模板
首先,我们是通过i从1到n的循环来依次表示前i件物品存入的状态。即:for i=1..N
现在思考如何能在dp[v]
表示当前状态是容量为v的背包所得价值,而又使dp[v]
和dp[v-c[i]]+w[i]
表示前一状态的价值?
逆序!这就是关键。
for i=1...N for v=V...0 f[v] = max{f[v],f[v-c[i]]+w[i]};
完全背包
完全背包(CompletePack): 有N种物品和一个容量为V的背包,每种物品都有无限件可用。第i种物品的费用是c[i]
,价值是w[i]
。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。
状态转移方程
dp[i][v] = max(dp[i-1][v-k*c[i]]+k*w[i]) (0<=k*c[i]<=V)
模板
dp[0...V]={0} for i=1...N for v=c[i]...V dp[v] = max{dp[v], dp[v-c[i]]+w[i]}
这个伪代码与01背包问题的伪代码只有v的循环次序不同而已。为什么这个算法就可行呢?
首先想想为什么01背包中要按照v递减的次序来循环?
让v递减是为了保证第i次循环中的状态dp[i][v]
是由状态dp[i-1][v-c[i]]
递推而来。换句话说,这正是为了保证每件物品只选一次,保证在考虑“选入第i件物品”这件策略时,依据的是一个绝无已经选入第i件物品的子结果dp[i-1][v-c[i]]
。
而现在完全背包的特点恰是每种物品可选无限件,所以在考虑“加选一件第i种物品”这种策略时,却正需要一个可能已选入第i种物品的子结果dp[i][v-c[i]]
,所以就可以并且必须采用v递增的顺序循环。
多重背包
多重背包(MultiplePack): 有N种物品和一个容量为V的背包。第i种物品最多有n[i]
件可用,每件费用是c[i]
,价值是w[i]
。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。
这题目和完全背包问题很类似。基本的方程只需将完全背包问题的方程略微一改即可,因为对于第i种物品有n[i]+1
种策略:取0件,取1件...取n[i]
件。令dp[i][v]
表示前i种物品恰放入一个容量为v的背包的最大价值。
状态转移方程
dp[i][v] = max(dp[i-1][v-k*c[i]]+k*w[i]) (0<=k<=n[i])
这篇关于背包问题的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-04TiDB 资源管控的对撞测试以及最佳实践架构
- 2024-07-03万字长文聊聊Web3的组成架构
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现