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

❤作者：那些年丶我们逃过的课

❤博客主页：那些年丶我们逃过的课的博客_CSDN博客-c++题目,c++学习记录,c++小游戏领域博主

❤码云gitee：我的码云 - Gitee.com

❤期待你的关注，如果觉得还可以的话，可以点赞评论支持一下，每个评论我都会回访的

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

2.分解子问题

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

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

​ 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])

3.数组 和 边界状态

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

4.计算顺序 从小到大

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

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

#include
using 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<=b;i++)	cin>>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< 
二维dp就是这样了，但是这个还是有一定局限，对于二维数组，数量少还好，数量一多就容易炸内存，那我们就需要进行改进，简化成一维数组。
 
 
 
那么我们就需要用到滚动数组了
 
 
一维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的背包的最大价值
 
初始化
 
注意，一维dp与二维dp计算顺序是不同的，详情见下 
倒序遍历是为了保证物品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
0
15
15
15
15
物品2
0
15
15
20
35
物品3
0
15
15
20
35
物品1价值15，物品2价值5，物品3价值20
 
物品3重量略大于物品2，所以在第5个背包重量时，把物品2换成物品3价值更高
 
大概就是这样的，表格比较简易，不太具体，大概可以理解到意思的。
 
一维dp代码 
#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< 
一维dp明显比二维更简洁
 
总结 
本次讲解了01背包问题的dp代码，分为二维dp和一维dp，一维dp明显比二维更简洁，也不容易爆内存。
 
2022.5.5 
18：57