动态规划
01背包问题
01背包问题特点所有物品只能用一次
dp问题分为两部分：状态表示和状态转移 。
状态表示
状态表示分为：集合和属性。
集合为：1.只考虑前i个物品且总体积不超过j的选项的集合
2.所求的属性，最大值或最小值
状态计算
将所有的集合分为两部分，选第i件物品和不选第i件物品
f[i][j]=f[i-1][j]; f[i][j]=f[i-1][j-v[i]]+w[i]; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ f[i][j]=f[i-1][j]; if(j>=v[i]){ f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]); } } } cout<<f[n][m]<<endl;//这点参考第7行
经过观察之后发现代码可以优化
f[i]仅用到了f[i-1]层
而且每次都用到上一层，则可以从大到小枚举，反之从小到大枚举
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]<<endl;
完全背包问题
完全背包问题的特点是所有物品可以无限使用
f[i][j]=max(f[i-1][j],(f[i-1][j-v]+w,f[i-1][j-2v]+2w,f[i-1][j-3v]+3w....))
观察后发现
上面那个max的后半部分可以表示为： f[i][j-v]=max(f[i-1][j-v],f[i-1][j-2v]+w,f[i-1][j-3v]+2w....)+w;
模板
for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ f[i][j]=f[i-1][j]; if(j>=v[i]){ f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]); } } }
经过观察后实现空间优化的算法
for(int i=1;i<=n;i++){ for(int j=v[i];j<=m;j++){ f[j]=max(f[j],f[j-v[i]]+w[i]); } }
