一、01背包问题

1.经典的01背包问题，采药

https://www.acwing.com/problem/content/425/

注意背包问题一定要理解，而不是只会背代码。对于01背包问题，本来是用两维i和j来存状态集合。但是i是可以优化掉的。但是为什么在优化掉之前，j可以正向或者反向枚举，而优化掉之后，j只能反向进行枚举？

这是状态转移方程所决定的。$f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+c[i])$，可以看到，第二维是$j-w[i]$,去掉一个维度之后变成$f[j]=max(f[j],f[j-w[i]]+c[i]$所以如果正向枚举的话，会用本次的i更新本次的i，这显然是错误的。而逆向枚举就不会有这样的问题。

2.一个反向的01背包，装箱问题

https://www.acwing.com/problem/content/1026/

3.二维的01背包，宠物小精灵之收服

https://www.acwing.com/problem/content/1024/

注意本题要计算剩余体力值，这时注意原背包的状态定义是所装的重量小于等于j，而不是恰为j，所以要从后往前枚举一下$while(k>0 && f[m1][m2-1]==f[m1][k-1]) k--;$

4.01背包求方案数，数字组合

https://www.acwing.com/problem/content/description/280/

5.01背包求具体方案，背包问题求具体方案

https://www.acwing.com/problem/content/12/

6.应用题向背包问题转化，关键在于将什么看做体积，将什么看做价值，开心的金明

https://www.acwing.com/solution/content/4538/

二、完全背包问题

1.完全背包的经典问题，买书

https://www.acwing.com/problem/content/1025/

同样地，注意完全背包去掉一维之后的正确性的证明。

2.完全背包求方案数，货币系统

https://www.acwing.com/problem/content/description/1023/

三、多重背包问题

1.单调队列优化，多重背包问题 III

https://www.acwing.com/problem/content/description/6/

2.二进制优化，庆功会

https://www.acwing.com/problem/content/description/1021/

同上题，下面引用背包九讲的代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 const int maxn=10005;
 7 int v[maxn],w[maxn];
 8 int f[maxn];
 9 int n,m,n1;
10 int main(){
11     
12     scanf("%d%d",&n,&m);
13     for(int i=1;i<=n;i++){
14         int x,y,s;
15         int t=1;
16         scanf("%d%d%d",&x,&y,&s);
17         while(s>=t){
18             v[++n1]=x*t;
19             w[n1]=y*t;
20             s-=t;
21             t*=2;
22         }
23         v[++n1]=x*s;
24         w[n1]=y*s;
25     }
26     
27     for(int i=1;i<=n1;i++)
28       for(int j=m;j>=v[i];j--){
29           f[j]=max(f[j],f[j-v[i]]+w[i]);
30       }
31     
32     printf("%d",f[m]);
33     
34     
35     return 0;
36     
37 }

三、混合背包问题

混合背包问题，混合背包问题

https://www.acwing.com/problem/content/7/

将01背包和完全背包都可以看做是多重背包问题，最后又可以把多重背包当做二进制01背包来做。

四、背包问题的初始化

1.体积最多是j:全部置为0，且每个v>0

2.体积恰好为j:先全部置为无穷，然后$f[0]=0$，每个v>0

3.体积至少为j:先全部置为无穷，然后$f[0]=0$

五、分组背包问题

1.分组背包经典问题，机器分配

https://www.acwing.com/problem/content/description/1015/

 分组背包是现实生活中和运筹学中比较常见的背包类型。

六、有依赖的背包问题

1.有依赖的背包问题经典问题，有依赖的背包问题

https://www.acwing.com/problem/content/10/

与其说这是一个比较特殊的背包问题，不如将之看做一个相对比较简单的树形dp问题

七、背包与dfs结合

参考笔者另一篇博客

https://blog.csdn.net/numb_ac/article/details/104493223

DP知识点总结6 背包DP（实时更新）

原文：https://www.cnblogs.com/talk-sea/p/14812437.html