动态规划知识点
背包问题
动态规划，算法课的时候其实就学过，但是在ACM中的应用远比算法课学的01背包等问题要多。
01背包问题
有 N 件物品和一个容量是 V的背包。每件物品只能使用一次。
第 \(i\)件物品的体积是 \(v_i\)，价值是 wi 。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。
接下来有 N行，每行两个整数 v**i,w**i，用空格隔开，分别表示第 i件物品的体积和价值。
输出格式
输出一个整数，表示最大价值。
简单理解题意，就是有一堆东西，他们有两个属性，一个是体积，一个是价值。
我们还有一个背包，背包只有一个属性，就是体积
要把选择一些东西装入背包中，每个东西只能选1次或者不选（这就是所谓的01）
最终目的是，在物品总体积不超过背包总体积的情况下，使得背包中的价值最大
分析dp的方法：状态表示（集合，属性） 状态计算
状态表示
集合：f[i,j]，表示从前i个物品中取，总体积不超过j，总价值
属性：总价值的最大值
状态计算
状态实际上就是针对上面我们分析出来的集合进行拆分，拆分成能够计算的更小的状态子集
对于一个f[i,j]我们可以认为他由两个子集构成，选第i个物品，不选第i个物品
如果不选第i个物品，f[i,j]=f[i-1,j]
如果选第i个物品，用子集来表示就是f[i,j]=f[i-1,j-v[i]]+w[i] 意思就是去掉这个物品的最大价值，加上这个物品的价值，就是现在的价值
综上我们有\(f[i,j]=max(f[i-1,j],f[i-1,j-v[i]]+w[i])\)
01背包一维优化
上述式子已经足以解决这个问题，但f[i,j]是一个二维矩阵，满足以下条件的状态转移方程可以优化为一维
- f[i,]仅仅依赖f[i-1,]
- f[i,j]依赖的f[i,g(j)]中的g(j)均在j的同侧
- 如果在j的右侧，就对j顺序遍历
- 如果在j的左侧，就对j逆序遍历
- 上述两条也不一定，需要具体问题具体分析，在01背包问题中是这样的
本质上是针对一个数组的重复利用，计算完f[i-1,]后，可以原地利用f[i-1,]的元素来计算下一级f[i,]的元素，那么这一维其实可以去掉
遍历顺序可以这样理解，以\(f[i,j]=max(f[i-1,j],f[i-1,j-v[i]]+w[i])\)为例，
我们通过一维优化把它优化成\(f[j]=max(f[j],f[j-v[i]]+w[i])\)以后
f[j]会依赖f[j-v[i]]也就是j左侧，那么在更新第i层的时候，j左边的应该还是i-1层的数据，没有被改动，因此从后向前遍历。
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int v[N];
int w[N];
int f[N];
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>v[i]>>w[i];
}
for(int i=1;i<=n;i++)
{
// for(int j=m;j>=v[i];j--)
// {//j=0需要初始化
// f[j]=max(f[j],f[j-v[i]]+w[i]);
// }
for(int j=m;j>=1;j--)
{
//这里要考虑0是因为，j=v[i]时，f[0]=0，第二个式子代表的就是只选第i个物品
if(j>=v[i])
{
f[j]=max(f[j],f[j-v[i]]+w[i]);
}
}
}
cout<<f[m];
}