背景

01背包是背包问题的基础数学模型，属于典型的动态规划问题。该问题描述为在容量为V的背包中装入n件物品（每件仅有体积和价值属性），
每个物品只能选择放入或不放入，目标为获得最大总价值且总体积不超过背包容量。
学习基本01背包问题对我们了解动态规划有很大的帮助，话不多说，直接上代码.

01背包代码

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
// Bag
// 动态规划： 主要推出状态转移方程
// 01背包容量固定， 物品有容量+价值
// 状态转移数组dp[i][j] 表示前i个物品放入重量为j的背包能装的最大价值
// 物品重量： 2 3 4 5； 价值：3 4 5 8
// dp[i][j] 1. 不放入i物品(放不下)， dp[i-1][j]; 2. 放入i物品， dp[i-1][j-w[i]]
func Bag(weight []int, values []int, cap int) {
	// 初始化数组
	dp := make([][]int, len(values)+1)
	for index := range dp {
		dp[index] = make([]int, cap+1)
	}
	for index := 1; index <= len(values); index += 1 {
		for j := 1; j <= cap; j += 1 {
			if weight[index-1] > j { // 放不下
				dp[index][j] = dp[index-1][j] // 不放入index个物品
			} else {
				noPut := dp[index-1][j] // 不放入的价值
				// dp[index-1][j-weight[index-1]] 要找到 没放当前商品的时候的最大值
				// index-1表示上一个商品; j-weight[index-1] 表示没有放入当前商品时候的最大价值
				put := dp[index-1][j-weight[index-1]] + values[index-1] // 放入的价值
				dp[index][j] = max(noPut, put)
			}
		}
	}
	for i := 0; i <= len(values); i += 1 {
		for j := 0; j <= cap; j += 1 {
			fmt.Printf("%d ", dp[i][j])
		}
		fmt.Println()
	}
}

转移方程

01背包的状态转换方程

f[i,j] = Max{ f[i-1,j-Wi]+Pi( j >= Wi ), f[i-1,j] }

大家都知道01背包的转移方程其实不难，但怎么理解呢？

动态规划算法解决此问题的核心思想是：背包容量为1时所能获得的最大收益是很容易计算的，在此基础上，可以推算出背包容量为2、3、4…所能获得的
最大收益。建立如下这张表格，依次将各个商品装入不同承重的背包中，计算出它们所能获得的最大收益。

商品种类 背包容量 – – – – – – – – –
商品种类 0 1 2 3 4 5 6 7 8 9
不装任何商品 0 0 0 0 0 0 0 0 0 0
商品一（容量2，权重/价值3） 0(装不下) 0(装不下) 3 3 3 3 3 3 3 3
商品二（容量3，权重/价值4） 0(装不下) 0(装不下) 3(只能装第一个) 4 + 0(放入该商品) 或者 3(不放入) —- —- —- —- —- —-
商品三（容量4，权重/价值5） 0(装不下) 0(装不下) 3 —- —- —- —- —- —- —-
商品四（容量5，权重/价值8） 0(装不下) 0(装不下) 3 —- —- —- —- —- —- —-

状态转移是按照背包容量/商品种类一点一点增大来比较的;

首先要清楚f[i, j]代表什么？

f[i, j] 代表容量为j的背包，有i个商品的情况下，所能获取的最大价值，如上表所示：

f[0, j] 没有任何商品 就都是0

f[1, j] 只有一件商品，只要装的下 最大价值就是商品一的价值

f[2, j] 两件商品,依次判断容量

随着商品的增多 总结出规律 即状态转移方程;

第一行只有一个商品的时候，装不下就是0，装的下就是第一个商品的价值，如上表是3；

第二行 有两个商品，容量一点一点增大，装不下商品二的时候，最大价值就是只有商品一的最大价值；注意临界点，当可以放入第二个商品的时候，
需要计算两种：

一种是不放入第二个商品，因为第一个商品可能价值 比第二种高；

另一种是放入该商品，需要计算放入该商品后剩余容量能够存放的最大价值;剩余容量的最大价值就是只有商品一
且容量为当前容量(商品二背包容量为3)减去商品二的容量(3)位置 即：商品一容量0的位置；
计算以上这两种方式 最大的价值 放入并计算总的最大价值

结语

01背包问题是动态规划经典的算法，理解01背包问题，能够让我们对动态规划有更进一步的理解。
当然还有很多的变形，后续逐步学习。