背包问题（动态规划）
题单介绍
首先看一下这道例题：[采药](https://www.luogu.com.cn/problem/P1048)
简单来说，就是现在有一个背包，最大的容积为m。有n件物品，每件物品都有体积w和价值v。从中选择若干件物品，使得所选物品的体积之和不超过背包容量，而且价值之和最大。求最大价值。
这道题很显然的能想到用搜索去做，每次枚举第i件物品选或不选，枚举完n件物品后，求出体积之和与价值之和。并更新答案。
但是由于搜索的时间复杂度为$O(2^n)$。当n大于30后，就会超时。
我们考虑一下当我们做出一次选择后，问题有什么改变。
* 如果我们不选第n个物品，那么就可以把最后一个物品去掉，n就可以减去1。
* 如果我们选第n个物品，那么也可以把最后一个物品去掉，而且背包的容量减少最后一个物品的体积w，答案加上价值v。
所以，当问题规模减小时，物品个数和背包容积两个参数会改变。那么我们就可以用这两个参数来表示子问题。
即dp[n][m]表示n个物品，容量为m时的最大价值。
* 当选第n个物品时，dp[n][m]=dp[n-1][m-w[n]]+v[n]。
* 当不选第n个物品时，dp[n][m]=dp[n-1][m];
所以我们在上面两个选项中选择更大的那个就行了。
根据上面的状态转移方程，我们可以写出以下代码：
```cpp
递归写法：
int f(int n,int m){
if(n<=0||m<=0)return 0;
if(dp[n][m]!=-1)return dp[n][m];
int t1= m>=w[n]?f(n-1,m-w[n])+v[n]:0;
int t2=f(n-1,m);
dp[n][m]=max(t1,t2);
return dp[n][m];
}
printf("%d\n",f(n,m));
循环写法：
for(int i=1;i<=n;i++){
for(int j=0;j<=m;j++){
if(j>=w[i]&&dp[i-1][j-w[i]]+v[i]>dp[i-1][j])
dp[i][j]=dp[i-1][j-w[i]]+v[i];
else dp[i][j]=dp[i-1][j];
}
}
printf("%d\n",dp[n][m]);
```
做完上面的问题，再看看这道题：[P1616](https://www.luogu.com.cn/problem/P1616)
不同于之前那道题。这道题对于每种物品都可以拿无穷多次。那我们再用之前的状态转移方程就不对了。
这道题我们也可以对选择进行分类：
* 如果不拿第n件物品，那么我们只要考虑前n-1件物品即可。
* 如果拿第n件物品，那么我们至少拿1个。我们就先拿走1个，拿不拿更多我们可以之后再判断。所以还要考虑这n件物品。
即dp[n][m]表示n个物品，容量为m时的最大价值。（粗体的地方为与之前不一样的地方）
* 当不选第n个物品时，dp[n][m]=dp[n-1][m];
* 当选至少1件第n个物品时，dp[n][m]=dp[**n**][m-w[n]]+v[n]。
更多背包问题，可以查看[背包九讲](https://cdn.jsdelivr.net/gh/tianyicui/pack@master/V2.pdf)
[背包问题](https://www.luogu.com.cn/blog/RPdreamer/bei-bao-wen-ti)