背包DP
题单介绍
[oi-wiki.org/dp](https://oi-wiki.org/dp/knapsack/#0-1-%E8%83%8C%E5%8C%85)
注意根据原理搜索是能转DP的，DP想不出来的时候暴搜剪枝试试。
## 贪心对比
部分背包-每个物品可拆分，不是整体选或者不选
## 01背包
[初步理解博客](https://blog.csdn.net/lllsure/article/details/144428762)
- [P2240 【深基12.例1】部分背包问题](https://www.luogu.com.cn/problem/P2240)
- [P1048 [NOIP 2005 普及组] 采药](https://www.luogu.com.cn/problem/P1048)
- [P2871 [USACO07DEC] Charm Bracelet S](https://www.luogu.com.cn/problem/P2871)
- [P2340 [USACO03FALL] Cow Exhibition G](https://www.luogu.com.cn/problem/P2340)
- [P5662 [CSP-J2019] 纪念品](https://www.luogu.com.cn/problem/P5662)
## 完全背包
- [P1616 疯狂的采药](https://www.luogu.com.cn/problem/P1616)
- [P1853 投资的最大效益](https://www.luogu.com.cn/problem/P1853)
## 多重背包
- [P1776 宝物筛选](https://www.luogu.com.cn/problem/P1776)
## 混合背包
- [P1833 樱花](https://www.luogu.com.cn/problem/P1833)
## 二维费用背包
- [P1507 NASA的食物计划](https://www.luogu.com.cn/problem/P1507)
- [P1855 榨取kkksc03](https://www.luogu.com.cn/problem/P1855)
- [P8548 小挖的买花](https://www.luogu.com.cn/problem/P8548)
## 分组背包
- [P1757 通天之分组背包](https://www.luogu.com.cn/problem/P1757)
## 有依赖背包
- [P1064 [NOIP 2006 提高组] 金明的预算方案](https://www.luogu.com.cn/problem/P1064)
[NOIP2006 提高组] 金明的预算方案.题解是直接枚举方案当分组转01背包做。(本来在瞎搞个更通用的，目前给的代码还只能处理两层高的森林，如果是更复杂的树形依赖，附件还有主从关系，就在calculateGroup里继续递归计算组合。还可以用二进制来枚举子集组合状态节省STL缓存空间，但是时间咋省待进化）
- [P2014 [CTSC1997] 选课](https://www.luogu.com.cn/problem/P2014) 正经树形依赖背包模板题
## 泛化背包
- [P1336 最佳课题选择](https://www.luogu.com.cn/problem/P1336)
- [P1417 烹调方案](https://www.luogu.com.cn/problem/P1417)
最佳课题选择还有个贪心+差分的做法by CZB，单调序列才可以这么做
```cpp
#include<bits/stdc++.h>
using namespace std;
long long n,m,a,b,k,w[4010],sum,dream;
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>a>>b;
dream=0;
w[k++]=a;
dream=a;
for(int j=2;j<=n;j++){
long long jj=j;
for(int o=1;o<b;o++)jj*=j;
w[k]=a*jj-dream;
dream=a*jj;
k++;
}
}
sort(w,w+k-1);
//for(int i=0;i<=k;i++)cout<<w[i]<<" ";
//cout<<endl<<endl;
for(int i=0;i<n;i++)sum+=w[i];
cout<<sum<<endl;
return 0;
}
```
## 变形1-方案可行性
- [P8646 [蓝桥杯 2017 省 AB] 包子凑数](https://www.luogu.com.cn/problem/P8646)
- [P2842 纸币问题 1](https://www.luogu.com.cn/problem/P2842)
## 变形2-计算方案数
- [P1077 [NOIP 2012 普及组] 摆花](https://www.luogu.com.cn/problem/P1077)
- [P1164 小A点菜](https://www.luogu.com.cn/problem/P1164)
- [P2840 纸币问题 2](https://www.luogu.com.cn/problem/P2840)
- [P2834 纸币问题 3](https://www.luogu.com.cn/problem/P2834)
## 变形3-输出方案
还没找到特别完全模板的背包输出方案题
可参考输出最长公共子序列的 AT_dp_f LCS
可参考变形线性DP输出方案 P1854 花店橱窗布置-非0/1背包，每个物品必须选而且选择没有代价限制
- [AT_dp_f LCS](https://www.luogu.com.cn/problem/AT_dp_f)
- [P1854 [IOI 1999] 花店橱窗布置](https://www.luogu.com.cn/problem/P1854)
# 草稿-这些题不重要
基础题目
•P1048 01背包：每件物品只有选和不选
两种状态，是最经典的背包问题目。
• P1616 完全背包：每件物品可以选择无限
个目，。
• U280382多重背包：每件物品有具体的
数量限制目。
进阶题目
· P1833 混合背包：结合了01背包、完全
背包和多重背包的特点目。
• P1855二维费用背包：除了重量限制
外，还有另一种消耗物的限制目。
•P1757分组背包：物品被分组，每组内只
能选择一件物品目。
• P1064依赖背包：物品之间存在依赖关
系，选择某个物品可能需要先选择其依赖
的物品目。
• P1336泛化物品背包：每个物品的价值
随分配的重量变化而变化目、。