DP动态规划入门学习记录（三）——01背包

题目简介（01背包）

有n个物品和一个容量为m的背包，每个物品的价值为c[i]，体积为w[i]，要求选择一些物品放入背包中，使物品总体积不超过m的前提下，物品的总价值最大，求最大总价值。

二维dp

按照一般解法而言，我首先思考的是将价值除以体积的值排序。这样应该是可以的，就是有些麻烦，并不是最优解。

动态规划思路分析：

1.$f[i][j]$表示将前i个物品放入载重为j的背包

2.分解子问题

​ 1）不放 $f[i][j]=f[i-1][j]$

​ 2）放 $f[i][j]=f[i-1][j-w[i]]+v[i]$

​ $f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i])$

3.数组 和 边界状态

​ $f[0][0]=0f[0][n]=f[m][0]=0$

4.计算顺序 从小到大

5.结果 $f[m][n]$即为将m个物品放入载重为n的背包的最大价值

分解子问题时，第一次我想的时候是很费脑筋的，弄懂了这类问题你就都明白了，你品，你细品。

举例：

二维dp代码

#includeusing namespace std;int w[1005],v[1005];int f[1005][1005];int main(){int a,b;cin>>a>>b;//a为背包载重，b为物品个数for(int i=1;i>w[i]>>v[i];f[0][0]=0;for(int i=1;i<=a;i++) f[0][i]=0;for(int i=1;i<=b;i++) f[i][0]=0;for(int i=1;i<=b;i++){for(int j=1;j<=a;j++){if(w[i]<=j){f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i]);}else f[i][j]=f[i-1][j];}}cout<<f[b][a];return 0;}

二维dp就是这样了，但是这个还是有一定局限，对于二维数组，数量少还好，数量一多就容易炸内存，那我们就需要进行改进，简化成一维数组。

那么我们就需要用到滚动数组了

一维dp分析（滚动数组）

在使用二维数组的时候，递推公式：$f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i])$;

其实可以把f[i - 1]那一层拷贝到f[i]上，表达式就是：$f[i][j]=max(f[i][j],f[i][j-w[i]]+v[i])$;

与其把f[i - 1]这一层拷贝到f[i]上，不如只用一个一维数组了，只用f[j]。

滚动数组需要满足的条件是上一层可以重复利用，直接拷贝到当前层。

1.$f[j]$表示载重为j的背包能获得的最大价值

2.分解子问题

​ 1）不放 $f[j]=f[j]$

​ 2）放 $f[j]=f[j-weight[i]]+v[i]$

​ $f[j]=max(f[j],f[j-weight[i]]+v[i]);$

3.数组 和 边界状态

​ $f[0]=0$

4.计算顺序 从右到左

5.结果 $f[n]$即为载重为n的背包的最大价值

初始化

注意，一维dp与二维dp计算顺序是不同的，详情见下

倒序遍历是为了保证物品i只被放入一次，具体可以自己打代码尝试，说多了也不好理解，画个图，测试一下就懂了

for(int i=1;i=w[i];j--)//背包重量遍历    {f[j]=max(f[j],f[j-w[i]]+v[i]);     }}

具象表格：

物品1价值15，物品2价值5，物品3价值20

物品3重量略大于物品2，所以在第5个背包重量时，把物品2换成物品3价值更高

大概就是这样的，表格比较简易，不太具体，大概可以理解到意思的。

一维dp代码

#includeusing namespace std;int main(){    int a,b;//a为背包载重，b为物品个数    int w[1005],v[1005];    int f[1005]={0};//定义dp数组并初始化为0    cin>>a>>b;    for(int i=1;i>w[i]>>v[i];    for(int i=1;i=w[i];j--)//背包重量遍历    {f[j]=max(f[j],f[j-w[i]]+v[i]);    }}    cout<<f[a];    return 0;}

一维dp明显比二维更简洁

总结

本次讲解了01背包问题的dp代码，分为二维dp和一维dp，一维dp明显比二维更简洁，也不容易爆内存。

2022.5.5

18：57