01背包-滚动数组

dp[i][j]是二维数组，从逻辑上来讲确实更好理解，但是代码上可以却是有优化空间，可以把dp[i][j]二维数组优化成dp[i]一维数组->就是滚动数组

在使用二维数组的时候，递推公式：

1

dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight(i)]+vlaue(i))

再来看看,dp[i][j]都是依赖正上方和左上方的数据来推导出,也就是说只依赖dp[i-1]层的数据计算而来,那么其实dp[i-1]层以上的数据都是不需要了,那么就可以直接一维数组,直接把dp[i-1]层的数据复制到dp[i]层即可

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

1. 递推公式就可以写成

1

dp[j]=max(dp[j],dp[j-weight(i)]+vlaue(i))

1. 重新对dp[j]数组进行定义： dp[j] : 当背包容量为j的时候,背包可以装入的最大价值dp[j]
2. dp[j]初始化：当背包容量j=0时,那背包可以装入的最大价值dp[j]为0，而从推导公式来看,都是取较大的一个,那么题中的价值都是非负数的话,把dp[j]都初始为0即可
3. 遍历顺序：

1
2
3
4
5

   for(int i=0 ; i<num ; i++){
        for(int j=maxWeight ; j>=weight[i] ;j-- ){
            dp[j] = max( dp[j] , dp[j-weight[i]]+values[i]);
        }
    }

和二维数组一样,都是先遍历物品i再遍历重量j,但j必须是从大到小, 如果j从小到大,那么就会出现物品重复放入

1
2
3
4
5
6

当i=0时，weight[0]=1，value[0]=15,dp[j]是全部初始化为0
j=0，dp[0]=0
j=1，dp[1]=15
j=2, dp[2]=30
j=3, dp[3]=45
j=4, dp[4]=60

从这里就能看到,物品0被重复的放入，不符合要求，再看看j从大到小的情况

1
2
3
4
5

当i=0时，weight[0]=1，value[0]=15,dp[j]是全部初始化为0
j=4,dp[4]=15
j=3,dp[3]=15
j=2,dp[2]=15
j=1,dp[1]=15

保证了物品只放入了一遍，此时的dp[j]={0,15,15,15,15}

1
2
3

当i=1时，weight[1]=3，value[1]=20
j=4,dp[4]=35
j=3,dp[3]=20

保证了物品只放入了一遍，此时的dp[j]={0,15,15,20,35}

1
2

当i=2时，weight[2]=4，value[2]=30
j[4],dp[4]=35

也是保证了物品只放入一遍，此时的dp[j]={0,15,15,20,35} 把三次循环的dp[j]结果整合一下，其实就和二维数组一样的结果了

完整代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

#include <iostream>
using namespace std;

#include <stdio.h>
#include <vector>
#include <math.h>

int maxWeight=4;
int num=3;
vector<int> weight={1,3,4};
vector<int> values={15,20,30};
vector<int> dp(5,0); //dp[j]全部初始化为0

int main(){
    for(int i=0 ; i<num ; i++){
        for(int j=maxWeight ; j>=weight[i] ;j-- ){
            dp[j] = max(dp[j] , dp[j-weight[i]]+values[i]);   
        }
        for(int index=0 ;index<dp.size();index++){
            printf("%d ",dp[index]);
        }
        printf("\n");
    }
    printf("max=%d\n",dp[maxWeight]);
    return 0;
}

细节点

1. 在二维数组下遍历，是要求dp[i][j]都是依赖正上方和左上方的数据来推导出，所以j是可以从小到大实现，但是在滚动数组下，每一层dp[j]都会被覆盖掉了，没有上一层的数据可以依赖了，j只能从大到小，防止物品i重复放入
2. 能否交换遍历的顺序呢？
   • 并不可以，在滚动数组下，只能先物品i再容量j
   • 以前可以验证：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

先j再i,dp[j]初始都为0
j=4,i=0
dp[4]=max(dp[4] , dp[4-weight(0)]+values[0])=15
j=4,i=1
dp[4]=max(dp[4] , dp[4-weight(1)]+values[1])=20
j=4,i=2
dp[4]=max(dp[4] , dp[4-weight(2)]+values[2])=30

j=3,i=0
dp[3]=max(dp[3] , dp[3-weight(0)]+values[0])=15
j=3,i=1
dp[3]=max(dp[3] , dp[3-weight(1)]+values[1])=20
j=3,i=2
dp[3]=max(dp[3] , dp[3-weight(2)]+values[2])=20

在先背包容量j再物品i的下，就等于是再当前容量j下，可以放入最大的单个物品时那个，即：背包里只放入了一个物品。