01背包
01背包是一个经典的动态规划问题，0代表不选，1代表选，其思想就是给定一个背包的容量和一些物品的重量和价值，问怎样选择物品装入背包才能让价值最大化。
| 物品 | 重量 | 价值 |
|---|---|---|
| 1号物品 | 2 | 1 |
| 2号物品 | 3 | 3 |
| 3号物品 | 4 | 5 |
| 4号物品 | 7 | 9 |
既然01背包是一个动态规划问题，那么五步要列出来：
- 确定状态
- 划分阶段-根据阶段确定求解顺序
- 决策选择-动态转移方程
- 边界条件-起点设置
- 求解目标
因为01背包问题就只有一个阶段，所以第2步就不需要了。
1确定状态：
对于初学者而言，二维数组dp[ ][ ]肯定是最好的选择，其中dp[i][j]表示前i个物品中能装入容量为j的背包的最大价值。
3决策选择-动态转移方程：
对于动态规划问题，有一个很好的方法：选还是不选，是选的价值更大，还是不选的价值更大。对此，我们可以列一下表格： （i为行，j为列）
| w | v | j/i | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|---|---|
| 2 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| 3 | 3 | 1 | 0 | 0 | 0 | 0 | 0 |
| 4 | 5 | 2 | 0 | 1 | 1 | 1 | 1 |
| 7 | 9 | 3 | 0 | 1 | 3 | 3 | 3 |
| 4 | 0 | 1 | 3 | 4 | 4 |
我们以第3行第3列的价值为例。如果我们不选，那么价值就是前i-1个物品能装入容量为j的最大价值；如果我们选，那么价值就是前i-1个物品的最大价值及其背包容量j-w[i]的容量+当前物品的价值v[i]。由此我们可以得出动态转移方程：
因此01背包问题（模板题）的核心代码为：
if(j>=w[i]){//如果你能装得下第i件物品
f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i]);//判断是选的价值更大还是不选的价值更大
}else{//不能装得下第i件物品
f[i][j]=f[i-1][j];//那么就只能不选了
}4边界条件-起点设置：
当i=0时，也就是物品数量为0时，自然也就没有价值，所以f[0][j]=0；当j=0时，也就是背包容量为0时，自然也就没有价值，所以f[i][0]=0。
5求解目标（返回结果）：
最终背包能够装下的最大价值即为 dp[n][w]，其中 n 表示物品数量，w 表示背包容量。
综上所述，使用动态规划算法可以在 O(nw) 的时间复杂度内解决背包问题，其中 n 表示物品数量，w 表示背包容量。
下面就是01背包问题（模板题）的标准代码：
//01背包问题（模板）
#include<iostream>
using namespace std;
int n,m;//n为容量，m为种类
int w[40];//重量
int v[40];//价值
int dp[40][210];//dp[i][j]为前i件物品，容量为j的最大价值
//dp[][]的初始值默认为0
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>w[i]>>v[i];
//读入重量与价值
}
//dp[i][j]=max(f[i-1][j],f[i][j-w[i]]+v[i])
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
if(j>=w[i]){//如果你能装得下第i件物品
dp[i][j]=max(dp[i-1][j],dp[i][j-w[i]]+v[i]);
//代入动态转移方程，判断是选的价值更大还是不选的价值更大
}else{//背包已经装不下了
dp[i][j]=dp[i-1][j];
//f[i][j]为前i项物品的最大价值
}
}
}
cout<<dp[m][n];//输出问题的最大价值
//时间复杂度为 O(nw)
return 0;
}最后的最后，给出两道基础题给读者做一做：
01背包问题
采药
（剩下的一些优化及其其它解题方法会在后面补上）