01背包

动态规划必备5步骤!

1. 确定dp数组（dp table）以及下标的含义
2. 确定递推公式
3. dp数组如何初始化
4. 确定遍历顺序
5. 举例推导dp数组

参考链接

动态规划的解题步骤

01背包

背包的最大重量为4，每个物品只能最多装一次或者不装，问装满这个背包的最大价值是多少？

暴力解法

回溯算法，枚举所有情况，如果是n个物品，那么时间复杂度是2^n

动态解法

1. 确定dp数组的以及下标的含义

1. dp[i][j]的值是价值，i是物品的编号，j是背包重量
2. [0,i]之间任取放进容量为j的背包里

2. 确定递推公式

dp[i][j]是任取0到i之间物品放入背包重量为j的价值

不放入第i物品

1. 当背包重量为j并j>=weight(i),那么得出： dp[i][j]=dp[i-1][j]
2. 当背包重量为j并j<weight(i),那么实际上无法放入i物品，那么得出： dp[i][j]=dp[i-1][j]

放入第i物品

当背包重量为j并j>=weight(i)，要把物品i放入，那么j就要有weight(i)的空位，就要等于在0到i-1物品之间，背包大小为j-weight(i)的价值最大再加上values(i)，所以得出： dp[i][j] = dp[i-1][j-weight(i)] + values(i)

把上述合并在一起，得出：

1

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

3. dp数组如何初始化

关于初始化，一定要和dp数组的定义吻合，否则到递推公式的时候就会越来越乱。

1. 当背包重量j为0的时候，什么物品都无法放入，价值为0,所以dp[i][0]=0
2. 当选取第0个物品的时候，只有当背包重量j大于等于weight(0)的时候才能把物品0放入，所以dp[0][j]=values(0),j>=weight(0)
3. 初始化的结果如下

1
2
3
4
5
6
7
8
9
10

for(int j=0;j<=maxWeight;j++){
    if(j>=weight[0]){
        dp[0][j] = values[0];
    }else{
        dp[0][j]=0;
    }
}
for(int i=0;i<weight.size();i++){
    dp[i][0]=0;
}

4. 确定遍历顺序

从上初始化结果的表格来看，有物品和重量两个维度，个人觉得从物品上先遍历会更好理解,代码如下：

1
2
3
4
5
6
7
8
9

for (int i = 1; i <weight.size() ; i++){
	for( int j=0 ; j<=maxWeight ; j++){
		if ( j < weight[i] ){
			dp[i][j] = dp[i-1][j];
		}else {
			dp[i][j] =  max ( dp[i-1][j] , dp[i-1][j-weight[i]]+values[i]);
		}
	}  
}

从递推公式来看，dp[i][j]是从dp[i-1][j]和dp[i-1][j-weight(i)]而来，在表中的位置来说，dp[i-1][j]在dp[i][j]的正上方，dp[i-1][j-weight(i)]在dp[i][j]的左边，也就是说，dp[i][j]需要的是左上角的数据

5. 举例推导dp数组

因为这个数据少，可以完全举例出来如下：

6. 完整代码

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
27
28
29
30
31
32
33
34

#include <iostream>
using namespace std;

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

//背包最大重量
int maxWeight=4;
//物品的重量
vector<int> weight={1,3,4};
//物品的价值
vector<int> values={15,20,30};
//初始化动态dp，已经对全部dp[i][j]初始化为0
vector<vector <int> > dp(weight.size(), vector<int>(maxWeight + 1, 0));

int main(){
    //
    for(int j=weight[0] ;j<=maxWeight;j++){
        dp[0][j] = values[0];
    }
    //先遍历物品，再遍历重量
    for (int i = 1; i <weight.size() ; i++){
      for( int j=0 ; j<=maxWeight ; j++){
        if ( j < weight[i] ){
            dp[i][j] = dp[i-1][j];
        }else {
            dp[i][j] =  max ( dp[i-1][j] , dp[i-1][j-weight[i]]+values[i]  );
        }
      }  
    }
    printf("max=%d\n", dp[2][4]);
	return 0;
}

细节点

1. 遍历的顺序是否能交换？

答案：是可以交换的 原因：还是先看如下表格，dp[i][j]都是依赖正上方和左上方的数据来推导出，

1. 当先遍历物品再遍历背包重量，就是先从左到右再从上到下，符合上述dp[i][j]的推导
2. 当先遍历背包重量再遍历物品，就是先从上到下再从左到右，依旧是符合dp[i][j]的推导

2. 背包重量是否可以从大到小？

答案：不可以 原因：当背包重量从大到小，等于是从右到左，没有数据来满足dp[i][j]的推导