动态规划_背包问题_01背包理论

参考: 代码随想录, 背包九讲

何为背包问题

背包问题是一类算法题目,其通常可以应用动态规划的方式进行处理,其解题思路汇总为背包问题.背包问题有多种, 可以总结如下图:

leetcode 中并没有对背包问题进行深度考核, 题目集中于 01背包 与 完全背包, 上图中可以发现,完全背包问题就是01背包中的1无限制, 所以01背包是背包问题中的基础;

01背包问题定义

有N件物品,和一个容量(衡量单位为重量)为W 的背包, 物品i 的重量为 weight[i], 价值为 value[i]. 每件物品仅能够装一次, 问这个背包可以装的最大价值是多少?

题目中的物品只有两个状态,取或者不取,那么利用回溯搜索的方式是可以解决的,但是时间复杂度是指数级别;所以利用动态规划处理是优选. 为了学习并了解01背包问题, 我采用代码随想录中的例子理解;

问题理解

问题定义

背包的容量为4, 物品的重量与价值如下表:

	重量	价值
物品 0	1	15
物品 1	3	20
物品 2	4	30

要求返回背包的最大价值;

二维dp数组解法

动态规划三步走

状态定义: dp[i][j] 表示为从 [0,i] 物品中选择放入容量为j 的背包中的最大价值, 那么最终的答案就是dp数组中右下角的数字;

状态的定义,上面的参考均没有解释为什么这么设计;

那么dp数组为二维数组:

	0	1	2	3	4
物品 0:
物品 1:
物品 2:

状态转移方程: 由于每一件物品的状态要么放,要么不放, 我们可以从这个角度推出状态转移方程来:

不放物品i: 此时 dp[i][j] 等价于 dp[i-1][j];
放物品i: 此时 dp[i][j] =dp[i-1][j-weight[i]] + value[i], 简单解释下: dp[i-1][j-weight[i]] 也就是在[0, i-1]的物品中放置在容量为[j-weight[i]] 的背包上的最大价值;

所以递推公式为:dp[i][j] = max( dp[i-1][j], dp[i-1][j-weight[i]] + value[i] )

边界情况:

边界的处理也是动态规划问题中着重点,因为其与问题的定义是息息相关的. 问题定义是 dp[i][j] 表示物品[0,i]放置在容量为j的背包中的最大价值;对于二维数组的边界情况, 我们需要处理的是dp[0][j] 与 dp[i][0] 的情况;

dp[0][j] : 指的是对于第一件物品放置在容量为j的背包上的最大价值; 那么当j 小于weight[0] 时, 为0 , 否则为 value[0];
dp[i][0]: 指的是对容量为0 的背包,放置前i件物品的最大价值, 那么应全部为0;

也就是如下表:

	1	2	3	4
物品 0:	15	15	15	15
物品 1:
物品 2:

初始化与遍历顺序

数组的初始化

首先数组的边界数组与上述一致,其次其他位置的数字在遍历过程中均会被重新赋值,所以其他位置可以为任意数字, 一般采用初始化为0;

	1	2	3	4
物品 0:	15	15	15	15
物品 1:	0	0	0	0
物品 2:	0	0	0	0

for (int j = 0 ; j < weight[0]; j++) {  
    dp[0][j] = 0;
}
for (int j = weight[0]; j <= bagweight; j++) {
    dp[0][j] = value[0];
}

数组的遍历顺序

对于二维数组,我们有两种选择,优先遍历物品或者优先遍历背包重量,对于本问题的状态定义来说,两种方式均是可以的;简单解释一下: 由状态转移方程dp[i][j] = max( dp[i-1][j], dp[i-1][j-weight[i]] + value[i] ), 我们发现,当前位置仅与左上方有关系, 我们需要保证的就是在遍历到当前位置时,上方与左前方位置均已确定即可;这里采用代码随想录中的两张图片,方便理解:

优先物品,其次背包:

优先背包,其次物品:

不过依照常见的遍历习惯,优先物品遍历,也就是优先行遍历是最常用的方式;对于背包问题,遍历顺序是需要讲究的,不可盲目按照习惯处理.

for(int i = 1; i < weight.size(); i++) { 
    for(int j = 0; j <= bagweight; 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]] + value[i]);
    }
}

算法实例

func test_2_wei_bag_problem1(weight, value []int, bagweight int) int {
	// 定义dp数组
	dp := make([][]int, len(weight))
	for i, _ := range dp {
		dp[i] = make([]int, bagweight+1)
	}
	// 初始化
	for j := bagweight; j >= weight[0]; j-- {
		dp[0][j] = dp[0][j-weight[0]] + value[0]
	}
	// 递推公式
	for i := 1; i < len(weight); i++ {
		//正序,也可以倒序
		for  j := weight[i];j<= bagweight ; j++ {
			dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]]+value[i])
		}		
	}
	return dp[len(weight)-1][bagweight]
}

func max(a,b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
	weight := []int{1,3,4}
	value := []int{15,20,30}
	test_2_wei_bag_problem1(weight,value,4)
}

一维dp数组解法

上面的二维数组解法中,从状态转移方程中可以发现dp[i][j] 仅取决于上一行dp[i-1]那么利用滚动数组处理一定是可行的.这也是01背包中最常适用的处理方式;

动态规划三步走

状态定义: dp[j] 定义为容量为 j 的背包所能够获得的最大价值;

状态转移方程: 这里与上面的介绍是一致的, 在遍历过程中,也是对物品i的取舍问题:

不放物品: dp[j] 不需要更新,本质与上述一致;
放物品: dp[j] = dp[j-weight[i]]+value[i];

综上: dp[j] = max(dp[j], dp[j-weight[i]] + value[i])

边界

对于一维数组的边界,也就是dp[0] 那么直接为0 即可;

初始化与遍历顺序

数组初始化

目前的状态定义为: dp[j] 为容量为j 的背包所能获得的最大价值; 那么在初始时, [1 : n] 为0即可, 这表示初始时背包还没有放物品,那就是0;

如果状态定义为: dp[j] 为容量j 的背包装满能获得的最大价值, 那么初始时, 没有装满的情况应当为 -∞ ,这表示一开始没有装, 自然应当为-∞;

对于初始化的讨论, 不可以简单的粗暴赋值, 一般取决于状态定义, 状态转移方程; 需要符合逻辑模型的定义;之后会进行整理;

遍历顺序

for(int i = 0; i < weight.size(); i++) { // 遍历物品
    for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    }
}

这里直接给出伪代码的结论:

不同于二维数组物品的遍历从1开始, 一维是从0开始遍历,这是由于一维数组的边界仅为dp[0],没有涵盖当前情况;

不同于二维数组容量采用从小到大的方式遍历, 一位数组的遍历顺序是从大到小处理;

倒序遍历是为了保证物品i只被放入一次！。但如果一旦正序遍历了，那么物品0就会被重复加入多次！

举一个例子：物品0的重量weight[0] = 1，价值value[0] = 15

如果正序遍历

dp[1] = dp[1 - weight[0]] + value[0] = 15

dp[2] = dp[2 - weight[0]] + value[0] = 30

此时dp[2]就已经是30了，意味着物品0，被放入了两次，所以不能正序遍历。

为什么倒序遍历，就可以保证物品只放入一次呢？

倒序就是先算dp[2]

dp[2] = dp[2 - weight[0]] + value[0] = 15 （dp数组已经都初始化为0）

dp[1] = dp[1 - weight[0]] + value[0] = 15

所以从后往前循环，每次取得状态不会和之前取得状态重合，这样每种物品就只取一次了。

那么问题又来了，为什么二维dp数组历的时候不用倒序呢？

因为对于二维dp，dp[i][j]都是通过上一层即dp[i - 1][j]计算而来，本层的dp[i][j]并不会被覆盖！

上面代码中优先遍历的物品,再遍历的背包容量, 这也是01背包 唯一允许的遍历方式; 那么为什么不能够优先遍历背包容量,再遍历物品呢?问题的点在于背包容量一定是倒序的, 这保证了01背包 的问题性质, 如果优先遍历背包容量, 那这里的唯一性将导致问题变为: 仅在背包中放置一个物品所获得的最大价值;

// 错误的01背包遍历顺序:
// 优先倒序遍历背包,将导致问题定义不一致
for j:= bagWeight; j >= weight[i] ; j-- {
    for i := 0; i<len(weight); i++ {
        if j >= weight[i] {
            dp[j] = max(dp[j], dp[j-weight[i]]+value[i])
        }
    }
}

算法实例

func test_1_wei_bag_problem(weight, value []int, bagWeight int) int {
	// 定义 and 初始化
	dp := make([]int,bagWeight+1)
	// 递推顺序
	for i := 0 ;i < len(weight) ; i++ {
		// 这里必须倒序,区别二维,因为二维dp保存了i的状态
		for j:= bagWeight; j >= weight[i] ; j-- {
			// 递推公式
			dp[j] = max(dp[j], dp[j-weight[i]]+value[i])
		}
	}
	//fmt.Println(dp)
	return dp[bagWeight]
}

func max(a,b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
	weight := []int{1,3,4}
	value := []int{15,20,30}
	test_1_wei_bag_problem(weight,value,4)
}