背包模型
01背包求最大价值
前提:背包容量受限
背景:商品具有(体积、价值)属性
目的:获取最大价值
问题描述:给定一些商品,每个商品具有一定的体积和价值;在一定的背包容量下去选择其中的一些商品,获取最大的价值v,求解这个最大价值v(01背包)
属性:Max
01背包最大价值方案计数(01背包求最大价值的扩展问题)
问题描述:给定一些商品,每个商品具有一定的体积和价值;在一定的背包容量下去选择其中的一些商品,获取最大的价值v,求解达成这个最大价值v的可选方案数目
属性:Count(计数)
01背包最大价值的具体方案(01背包求最大价值的扩展问题)
问题描述:给定一些商品,每个商品具有一定的体积和价值;在一定的背包容量下去选择其中的一些商品,获取最大的价值v,求解达成这个最大价值v的具体方案
属性:Max、具体方案
01背包满状态方案计数(换钱方案)
问题描述:给定一些商品,每个商品具有一定的体积;选择其中的一些商品使得其可以
恰好装满一定体积v的背包
,求可选择的方案数目
属性:Count(计数)
问题可以变形为:判断是否存在一种方案,可以填充满一定的空间
- AcWing 278. 数字组合 || 不可重复选择(01背包)
- AcWing 1023. 买书 || 可重复选择(完全背包)
- AcWing 1021. 货币系统 || 可重复选择(完全背包)
- AcWing 900. 整数划分 || 可重复选择(完全背包)
完全背包
给定一些物品,物品具有代价和价值,每个物品有无数多件,选择其中的一些物品,使得在一定代价w下获取最大的价值v,求解这个最大价值v(完全背包)
属性:Max
多重背包
给定一些物品,物品具有代价和价值,每个物品有一定的数量,选择其中的一些物品,使得在一定代价w下获取最大的价值v,求解这个最大价值v(多重背包)
属性:Max
优化方法:二进制优化、优先队列优化
混合背包
给定一些物品,物品具有代价和价值,有一部分物品有数量限制,另外一部分没有数量限制,选择其中的一些物品,使得在一定代价w下获取最大的价值v,求解这个最大价值v(混合背包)
分组背包
给定一些类别的物品,每一种类别下具有多种商品,每一类只能选择其下的一种商品,选择其中的一些物品,使得在一定代价w下获取最大的价值v,求解这个最大价值v(分组背包)
二维费用背包
前提:容量和承重受限的背包
背景:商品具有(体积、重量、价值)
目的:获取最大价值
问题描述:给定一些商品,每个商品具有一定的体积、重量和价值;在一定的背包容量和承重条件下,去选择其中的一些商品,获取最大的价值v,求解这个最大价值v(二维费用背包)
属性:Max
有依赖的背包
问题描述:给定一些商品,每个商品具有一定的体积和价值,商品之间存在依赖关系(即当购买A物品之前必须同时购买B物品),在一定的背包容量下,去选择其中的一些商品,获取最大的价值v;
属性:Max
序列DP
2023-04-09 updated