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

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

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

在使用二维数组的时候，递推公式： f [ i ] [ j ] = m a x ( f [ i − 1 ] [ 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]) f[i][j]=max(f[i−1][j],f[i−1][j−w[i]]+v[i]);

其实可以把f[i - 1]那一层拷贝到f[i]上，表达式就是： f [ i ] [ j ] = m a x ( f [ i ] [ j ] , f [ i ] [ j − w [ i ] ] + v [ i ] ) f[i][j] = max(f[i][j],f[i][j-w[i]]+v[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 ] f[j] f[j]表示载重为j的背包能获得的最大价值

2.分解子问题

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

​ 2）放 f [ j ] = f [ j − w e i g h t [ i ] ] + v [ i ] f[j]=f[j-weight[i]]+v[i] f[j]=f[j−weight[i]]+v[i]

​ f [ j ] = m a x ( f [ j ] , f [ j − w e i g h t [ i ] ] + v [ i ] ) ; f[j]=max(f[j],f[j-weight[i]]+v[i]); f[j]=max(f[j],f[j−weight[i]]+v[i]);

3.数组 和 边界状态

​ f [ 0 ] = 0 f[0]=0 f[0]=0

4.计算顺序 从右到左

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

初始化

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

for(int i=1;i<=n;i++)//物品遍历
{
    for(int j=m;j>=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价值更高

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

#include
using 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<=b;i++)	cin>>w[i]>>v[i];
    for(int i=1;i<=b;i++)//物品遍历
	{
    	for(int j=a;j>=w[i];j--)//背包重量遍历
    	{
    	   f[j]=max(f[j],f[j-w[i]]+v[i]); 
   		}
	}
    cout<