动态规划原理:
动态规划与分治法类似，都是把大问题拆分成小问题，通过寻找大问题与小问题的递推关系，解决一个个小问题，最终达到解决原问题的效果。但不同的是，分治法在子问题和子子问题等上被重复计算了很多次，而动态规划则具有记忆性，通过填写表把所有已经解决的子问题答案纪录下来，在新问题里需要用到的子问题可以直接提取，避免了重复计算，从而节约了时间，所以在问题满足最优性原理之后，用动态规划解决问题的核心就在于填表，表填写完毕，最优解也就找到
01背包问题解题过程
在解决问题之前，为描述方便，首先定义一些变量：Vi表示第 i 个物品的价值，Wi表示第 i 个物品的体积，定义V(i,j)：当前背包容量 j，前 i 个物品最佳组合对应的价值。同时背包问题抽象化（X1，X2，…，Xn，其中 Xi 取0或1，表示第 i 个物品选或不选）。
1、建立模型，即求max(V1X1+V2X2+…+VnXn)；
2、寻找约束条件，W1X1+W2X2+…+WnXn<capacity；
3、寻找递推关系式，面对当前商品有两种可能性：
①包的容量比该商品体积小，装不下，此时的价值与前i-1个的价值是一样的，即V(i,j)=V(i-1,j)；
②还有足够的容量可以装该商品，但装了也不一定达到当前最优价值，所以在装与不装之间选择最优的一个，即V(i,j)=max｛V(i-1,j)，V(i-1,j-w(i))+v(i)｝。
其中V(i-1,j)表示不装，V(i-1,j-w(i))+v(i) 表示装了第i个商品，背包容量减少w(i)，但价值增加了v(i)；
由此可以得出递推关系式：
j<w(i) V(i,j)=V(i-1,j)
j>=w(i) V(i,j)=max｛V(i-1,j)，V(i-1,j-w(i))+v(i)｝
关键点(也是困扰很久的地方，最好手推一遍)：
//V(i-1,j-w(i)) 表是如果加入第i个商品，则前（i-1）商品在容量（j-w（i）)时所容纳的最优值，换句话说，就是，再去掉第i 个商品容量后，前（i-1）个商品的价值最优值
比如：总体容量为V，总体物品数位N
N:4 V：5
n(i) v(i) 0 0+2
1 2 第一轮： V(i,j)=max｛V(i-1,j)，V(i-1,j-w(i))+v(i)｝==》V（1，5）=max{v(0,5),v(0,4)+v(1)}=2
2 4 第二轮 ：V（2，5）=max{v(1,4), v(1,3)+v(2)}=6 V(1,3)则是，加入第二件商品后，总容量减去第二件商品的容量的最优值 1
3 6 第三轮： V（3，5）=max{v(2,5), v(2,2)+v(3)}=8 v(2,2）是：加入第三件商品后，总容量减去第三件件商品的容量的最优值 2
4 5 第四轮： V（4，5）=max{v(3,5), v(3,0)+v(4)}=8 这时 v(3,0)+v(4)<v(3,5)
由此可以看出，动态规划需要维护一张全局表，记录每个状态下的最优值，从而不需要进行重复的计算。
进行一个完整的推导：
填表，首先初始化边界条件，V(0,j)=V(i,0)=0；
比如V(2,3)=max{v(1,3), V(1,0)+v(2)}=4 即加入第二件商品时,在容量为3 的情况下, 不加第二件 和 (加入第二件后的价值+容量减去第二件容量的价值)的最优值
实现代码如下(go语言实现)
package main
import "fmt"
var v []int //每个物品的价值
var w []int //每个物品的容量(重量)
var x []int //第N个物品选择拿或不拿
var m [][]int //当前最大的价值
var n, c int //物品数和背包容量
var mv int //最优值
//比较最大值
func max(a, b int) (result int) {
if a < b {
return b
} else {
return a
}
}
//寻找最优值
func traceback() {
for i := n; i > 1; i-- {
if m[i][c] == m[i-1][c] {
x[i] = 0
} else {
x[i] = 1
c -= w[i]
}
}
if m[1][c] > 0 {
x[1] = 1
} else {
x[1] = 0
}
}
func main() {
//从键盘输入物品数n,背包的最大容量c
fmt.Scan(&n, &c)
for i := 0; i < n+1; i++ {
//使用切片建立一个动态二位数组
arr := make([]int, c+1)
m = append(m, arr)
}
v = make([]int, n+1)
w = make([]int, n+1)
x = make([]int, n+1)
//从键盘输入每个物品的价值v[i]和容量w[i]
for i := 1; i <= n; i++ {
fmt.Scan(&w[i], &v[i])
}
//fmt.Println(v, w)
//初始化边界条件,即背包容量为0,物品数量为0
for i := 0; i <= n; i++ {
m[0][i] = 0
m[i][0] = 0
}
for i := 1; i <= n; i++ {
for j := 1; j <= c; j++ {
if j >= w[i] {
m[i][j] = max(m[i-1][j], m[i-1][j-w[i]]+v[i])
} else {
m[i][j] = m[i-1][j]
}
}
}
//寻找最优值,如果m[i][j]是最优值,则x[i]=1否则为0
traceback()
mv = 0
for i := 1; i <= n; i++ {
//fmt.Println(x[i])
mv += x[i] * v[i]
}
fmt.Println(mv)
}
参考博客:：https://blog.csdn.net/qq_38410730/article/details/81667885