欢迎大家来到IT世界,在知识的湖畔探索吧!
背包问题是最基础的动态规划问题,本文给出背包的模板代码。
约定
- 背包容量(Capacity): C
- 物品数目( Number of items): N
- 第 i 件物品的占用背包的空间容量(Capacity of item i, 也可以理解为Cost): c_i, 其中1≤i≤N
- 第i件物品的价值(Value of item i): v_i, 其中1≤i≤N
- F(i,j): 前i个物品, 容量为j的背包下能装的物品的最大价值, 是一个 (N+1)×(C+1) 的矩阵
01背包
第i个物品: 要么放0件,要么放1件
伪代码如下:
可视化如下:
上述步骤充分理解后,为节省存储空间,可用一维向量来存储,伪代码如下:
注意:
- 内层for循环的迭代顺序从大到小
- 矩阵第一行初始化有两种选择:
- 如果不要求装满背包,不装物品对应的价值全部为0,故第一行全部初始化为0;
- 如果要求恰好装满背包,除首元素外,对于j=1,2,…,C容量,不装物品不满足要求,全部初始化为一个负无穷大。
完全背包
对于完全背包问题,第i个物品: 可以放任意件,只要不超出背包容量。与01背包不同的,只在于内层for循环的迭代顺序,见下图红色部分:
二维可视化如下,仔细体会:
分组背包
物品有K组,每组内:物品互相冲突,最多选一件。
伪代码如下:
和01背包类似,只是多了一层循环,分别尝试一组内的物品。
依赖背包
- 考虑一个主件和它的附件(假设有n个)集合,可用策略: 2^n+1:
- 1: 不选主件
- 2^n: 选取主件后的策略数
- 所有策略都是互斥的,将该主件和它的附件集合对应的所有策略转换为 分组背包 中的一个物品组,每个物品(策略)有一个cost和value
- 所有费用相同的策略,只取价值最大的策略
- 对主件k的附件集合进行 01-恰好-背包, 得到费用为 0,1,⋯,C−c_k时,对应的最大价值 F
- 转换为一个物品组:
- 应用分组背包算法
注: 公式不太好输入,需要latex pdf版本的,可以私信我。
免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://itzsg.com/40577.html