从今天开始正式学习动态规划的篇章啦。每天都一定会更新一篇 主要参考书籍有《算法笔记》，acwing大雪菜-基础课，提高课。 其他有关的博客，以及题目。在引用的时候，我也会贴上去。 背包问题 滚动数组以及在DP中的应用–>一定要看一下，优化就是在这里。 首先对动态规划有一个字面上的了解：它是为了解决什么问题？ 动态规划是为了解决一类最优化问题的算法思想。简单来说，DP问题是为将一个复杂的问题分解成若干子问题，通过综合子问题的最优解来得到原问题的最优解。动态规划会将每个求解过的子问题的解记录下来，算是缓存的作用叭。
0/1背包问题描述： 有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
在闫老师的基础课中，分析过程如下，这算是最基本的分析套路：
在这里的集合中，状态表示： 状态表示的集合：涉及对物品的所有选法。条件是：不能超过我们规定的容量，其实就是背包的体积。 状态集合的属性：这里选取的是最大值—>max。
状态计算：（算是dp问题中，最最重要的了，找不对状态方程或者对状态方程理解错误，那是最操蛋的）：
这是最基础的背包问题，特点是：一个物品只有一件（或者理解为只能拿一次），在放入背包的过程中，可以选择放和不放。 用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。
这里对f[i][j]要有一个深刻的理解以及表述：将前i件物品放入容量为v的背包中。然后考虑集合呢？：若只考虑第i件物品的策略（放或不放）。对于对最后一个物品放还是不放：那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”，此时能获得的最大价值就是f [i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]。
那么集合的图如下：
比如我给一堆数据：
5 8 3 4 5 5 1 2 2 1 2 3 说明：表示5个物品，背包的大小是8.下面5行对应体积以及价值最大的价值应该是8
5 5 1 2 2 1那么从以上的分析，我们采用二维的解法，代码如下： 第一维度是选物品，第二维度是控制体积。 存在一个递推关系：
#include <iostream> using namespace std; int n,m;//n个物品，背包的体积为m const int N=1010; int w[N],v[N]; int f[N][N];//状态记忆 int main(){ cin>>n>>m; for(int i=1;i<=n;i++) cin>>v[i]>>w[i]; //这就是dp的核心了 for(int i=1;i<=n;i++){ for(int j=0;j<=m;j++){ //不选择第i件物品 f[i][j]=f[i-1][j]; //选择第i件物品，但是还是稍微去判断一下，万一背包装不下呢？ if(v[i]<=j) f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]); } } cout<<f[n][m]; return 0; }从以上的代码中，我们不妨再去思考一下： 以上的时间，时间复杂度为O(n*V)，空间复杂度是O(V) 在闫老师的讲解中，其实我觉得降维并没有特别理解。 还是从之前的状态转移方程出发：其实简单理解就是选还是不选。 d[i][j]=max(d[i-1][j],d[i-1][j-v[i]]+w[i])
那么我们发现，dp很重要的思路是递推。像是多米诺骨牌效应，上面的状态转移方程f[i][j]受f[i-1][j]的影响。那么，当计算f[i+1][j]就完全用不到f[i-1][j]了。因此开一个一位数组f[v]（即把之前的第一维i省去），枚举方向：i从1到n，体积v从V到0（这里是逆序）,那么状态转移方程为：
f[v]=max(f[v],f[v-v[i]]+w[i])这里还是很希望看一下滚动数组，不然直接就理解优化过程可能比较生涩。 逆序是为了保证更新当前状态时，用到的状态是上一轮的状态，保证每个物品只有一次或零次;
#include <iostream> #include <algorithm> using namespace std; const int N=1010; int v[N],w[N],f[N]; int n,m; int main(){ 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--){ f[j]=max(f[j],f[j-v[i]]+w[i]); } } cout<<f[m]; return 0; }