背包dp
作者：
asukaqaqzz
,
2022-02-22 20:03:46
,
所有人可见
,
阅读 214
背包问题分为
- 01背包
- 完全背包
- 分组背包
- 多重背包
- 计数类背包
- 混合背包
- 有依赖的背包
01背包
| 题目 |
题意 |
关键字/分析 |
题解 |
| 1024.装箱问题 |
有n个物品,求装入容积为V的箱子中,剩余的最小容积 |
“不超过”，剩余空间 |
|
| 1205.买不到的数目 |
给定两个糖果,他们最大不能凑到的整数是多少 |
bool,01背包 |
题解 |
| 二维费用的背包问题 |
求体积不超过V,重量不超过M的最大价值 |
二维费用 |
|
| 1022.宠物小精灵收服 |
有k个精灵球,血量m,求伤害<m能收服的最多妖怪树 |
二维费用,小于m |
题解 |
| 1020.潜水员 |
求氧气至少是n,氮气至少是m的最小气缸重量和 |
“至少”,二维费用 |
题解 |
| nc4i.爆炸的副卡洋洋洒洒 |
有n个魔法,每个魔法消耗为a,威力为b,求魔法消耗和恰好是k的倍数时的最大威力 |
01背包,取模运算 |
|
| 背包问题求具体方案 |
求最优解字典序最小的方案 |
求方案,拓扑序 |
题解 |
| 734.能量石 |
n个能量为e的石头,吃掉一个花s,每秒钟损耗l,求最大能量 |
推公式,01背包 |
题解 |
完全背包
| 题目 |
题意 |
关键字/分析 |
题解 |
| 532.货币系统 |
找出所有不能被自己以外的数表示出来的数的数量 |
bool型,结论 |
题解 |
分组背包
| 题目 |
题意 |
关键字/分析 |
题解 |
| 9.分组背包 |
同组内的决策互斥 |
模板 |
题解 |
| 487.金明的预算方案 |
选择一个物品必须先买他的主件,一个主件最多有2个附件,求钱为M时最多的价值 |
分组背包,DFS,二进制枚举 |
题解 |
多重背包
计数类背包
混合背包
| 题目 |
题意 |
关键字/分析 |
题解 |
| 混合背包 |
3种选择,01,多重,完全 |
模板 |
|
有依赖的背包
背包问题的恰好,至少,至多
