关于java:经典动态规划01-背包问题

前言

通过后面三篇动静布局文章的介绍，置信大家对动静布局、分治、贪婪有了充沛的了解，对动静布局的 3 个外围问题、其本质也有了理解。

纸上得来终觉浅，绝知此事要躬行。

那么明天开始咱们来聊聊具体的那些面试时常考的题目。

（还没有看过前三篇文章的同学齐姐叫你补课啦～）

（一）：初识动静布局

（二）：动静布局的 3 个外围问题

（三）：动静布局的实质

问题背景

月黑风高的夜晚，张三开启了法外狂徒模式：他背着一个可装载重量为 W 的背包去地主家偷东西。

地主家有 N 个物品，每个物品有分量和价值两个属性，其中第 i 个物品的分量为 wt[i]，价值为 val[i]。

问张三当初用这个背包装物品，最多能装的价值是多少？

举例：

N = 3 // 地主家有三样货色

wt = [2,1,3] // 每样货色的分量

val = [4,2,3] // 每样货色的价值

W = 4 // 背包可装载重量

算法应该返回 6.

因为抉择第一件物品和第二件物品，在分量没有超出背包容量下，所选价值最大。

如果每种物品只能选 0 个或 1 个（即要么将此物品装进包里要么不装），则此问题称为 0-1 背包问题；如果不限每种物品的数量，则称为无界（或齐全）背包问题。

明天这篇文章咱们只关注 0-1 背包问题，下一篇文章再聊齐全背包问题。

那咱们是如何抉择要装入的物品的？

思路初探

首先，品质很大价值很小 的物品咱们先不思考（放着地主家 金银财宝珍珠首饰 不偷，背进去一包煤 …，那也就根本辞别偷盗行业了 …）

而后呢？再思考 品质大价值也大 的？还是 品质较小价值也稍小 的？

咱们自然而然想到：装 价值 / 品质 比值最大的，因为这至多能阐明，此物品的“ 价质比”最大（也即贪婪算法，每次抉择以后最优）

那么这样装能保障最初装入背包里的价值最优吗？

咱们先来看一个例子：

假如有 5 个物品，N = 5，每种物品的品质与价值如下：

W : 20, 30, 40, 50, 60

V : 20, 30, 44, 55, 60

V/W: 1, 1, 1.1, 1.1, 1

背包容量为 100

如果按上述策略：优先选“价质比”最大的：即第三个和第四个物品

此时品质：40+50=90

价值：44+55 =99

但咱们晓得，此题更优的抉择策略是：选第一个，第二个和第四个

此时品质：20+30+50=100

价值：20+30+55=105

所以，咱们的“价质比”这种贪婪策略显然不是最优策略。

读过一文学懂动静布局这篇文章的读者会发现，之前文章中 兑换零钱 例子咱们最开始也是采取贪婪策略，但最初发现贪婪不是最优解，由此咱们引出了 动静布局。

没错，明天这题也正是 动静布局 又一经典的利用。

解题思路

依据动之前的文章咱们晓得，动静布局的外围即：状态 与状态转移方程。

那么此题的 状态 是什么呢？

状态

何为状态？

说白了，状态就是 已知条件。

重读题意咱们发现：此题的已知条件只有两个：

• 背包容量
• 可选的物品

题目要求的是在满足背包容量前提下，可装入的最大价值。

那么咱们能够根据上述状态定义出 dp 数组，即：

dp[i][w] 示意：对于前 i 个物品，以后背包的容量为w，这种状况下能够装的最大价值是dp[i][w]

咱们自然而然的思考到如下非凡状况：

当 i = 0 或 w = 0，那么：

dp0 = dp… = 0

解释：
对前 0 个物品而言，无论背包容量等于多少，装入的价值为 0；

当背包容量为 0 时，无论装入前多少个物品（因为一个都装不进去），背包里的价值仍旧为 0。

依据这个定义，咱们求的最终答案就是dp[N][W]

咱们当初找出了 状态 ，并找到了 base case，那么状态之间该如何转移呢（ 状态转移方程）？

状态转移方程

dpi 示意：对于前 i 个物品，以后背包的容量为w，这种状况下能够装的最大价值是dp[i][w]。

思考：对于以后第 i 个物品：

• 如果没有把第 i 个物品装入包里 （第 i 个物品 品质 大于以后 背包容量 ）：那么很显然，最大价值dpi 应该等于dpi – 1，没有装进去嘛，故以后背包总价值就等于之前的后果，即第i – 1 个物品之前的总价值。
• 如果把第 i 个物品装入了包里，那么 dpi 应该等于什么呢？

它应该等于上面两者里的较大值：

1. dpi – 1 // 前 i – 1 个物品，背包所装的最大价值
2. dp[i – 1]w – wt[i]] + val [i] // 以后第 i 个物品我装里边了，那么此时背包装入的总价值即为：以后第 i 个物品的价值 val [i] + 第 i 个物品之前，背包容量为w – wt[i]（w 减去以后第 i 个物品的品质）dp[i – 1]w – wt[i]] 时的价值

上述两个如果能够写成以下代码：

// 如果第 i 个物品品质大于以后背包容量
if (wt[i] > W) {dp[i][W] = dp[i-1][W];  // 继承上一个后果
} else {
// 在“上一个后果价值”和“把以后第 i 个物品装入背包里所失去价值”二者里选价值较大的
    dp[i][W] = Math.max(dp[i-1][W],dp[i-1][W-wt[i]] + val[i])
}

例子

咱们接来下再用一个具体的例子，来了解 状态和状态转移方程。

当初咱们有 4 个物品，物品对应的价值与品质别离如上图左侧所示：

6, 4

2，5

1, 4

8, 1

Step 1

咱们首先初始化一行和一列 0，别离对应dp0 和 dpi。

那么第一个问号处应该填什么呢？

咱们根据上述表述的状态转移关系来判断：

以后第一个物品的分量 4 > 背包容量，故装不进去，所以继承上一个后果。

上一个后果是什么呢？

就是第 i – 1个物品，也就是第 0 个，和 W = 1 时的价值：

if (wt[i] > W) {dp[i][W] = dp[i-1][W];  // 继承上一个后果
}

此时方框里的值为 0，故第一个问号这里应该填 0

Step 2

当初咱们走到了当背包容量 W = 2 的时候，此时以后 i (仍旧第一个物品)是否装进背包里呢？

咱们发现 4 > 2，此时还是装不进去，那么同样继承上一个后果。

上一个后果是 i 不变 (仍旧是第 0 个物品),W = 2，所以后果仍旧为 0。

Step 3

当初来到 W = 3，发现仍旧装不进去，所以填 0。

Step 4

下一步到 W = 4 这里了，

此时物品分量 4 = 4(背包容量)，能够装里，那么依照之前状态转移关系应该是：

else {
// 在“上一个后果价值”和“把以后第 i 个物品装入背包里所失去价值”二者里选价值较大的
    dp[i][W] = Math.max(dp[i-1][W],dp[i-1][W-wt[i]] + val[i])
}

Option A:

• 上一个后果 : dpi – 1，即dp0 = 0

Option B:

• 把以后第 i 个物品装入背包里所失去价值：dp[i – 1]W – wt[i]] + val [i]

此时第一个物品的分量为 4，背包容量为 4,

故要想装入分量为 4 的此物品，那么背包先前的容量必须为以后背包容量 – 以后物品容量：4 – 4 = 0。

咱们随即找到在没装入此物品（分量为 4，价值为 6）之前的dp[i -1]W – wt[i]] = dp0 = 0

那么dp[i -1]W – wt[i]] + val [i] = 0 + 6 = 6

6 和 0 抉择一个最大值，所以这里 问号处 应填入6

Step 5

下一步咱们来到 W = 5 这里，此时仍旧是第一个物品，品质 4 < 5(背包容量)，咱们能够装里边。

而后咱们在

Option A:

• 上一个后果：dp0 = 0

Option B:

• 把以后第 i 个物品装入背包里所失去价值：dp[i -1]W – wt[i]] + val [i]

此时第一个物品的分量为 4，背包容量为 5

故要想装入分量为 4 的此物品，那么背包先前的容量必须为：以后背包容量 – 以后物品容量：5 – 4 = 1，

咱们随即找到在没装入此物品 (分量为 4，价值为 6) 之前的dp[i – 1]W – wt[i]] = dp0 = 0

那么dp[i -1]W – wt[i]] + val [i] = 0 + 6 = 6

抉择一个最大值，即 6，所以此处应该填入 6

咱们依据以上 状态转系 关系，顺次能够填出空格其它值，最初咱们失去整个 dp 数组：

最初的 dp4：思考前四个物品，背包容量为 6 的状况下，可装入的最大价值，即为所求。

(留神 ：咱们在这里求的是 0-1 背包 问题，即某一个物品只能抉择 0 个或 1 个，不能多选！)

代码

依据以上思路，咱们很容易写出代码：

两层 for 循环

1. 外层循环 i 遍历物品(即前几个物品)：

for(int i = 1;i <=N;i++){...}

1. 内层循环 j 遍历 1~W(背包容量)之间的整数值：

而后写入状态转移方程

for(int j = 0;j <= W;j++){
        // 外层循环 i, 如果第 i 个物品品质大于以后背包容量
    if (wt[i] > W) {dp[i][W] = dp[i-1][W];  // 继承上一个后果
    } else {
        // 在“上一个后果价值”和“把以后第 i 个物品装入背包里所失去价值”二者里选价值较大的
        dp[i][W] = Math.max(dp[i-1][W],dp[i-1][W-wt[i]] + val[i])
    }
}

由此咱们给出残缺代码：

class solution{public int knapsackProblem(int[] wt,int[] val,int size){
                // 定义 dp 数组
                int[][] dp = new int[wt.length][size];
                // 对于装入前 0 个物品而言，dp 数组贮存的总价值初始化为 0
                for(int i = 0;i < size;i++){int[0][i] = 0;
                }
                // 对于背包容量 W = 0 时，装入背包的总价值初始化为 0
                for(int j = 0;j < size;j++){int[j][0] = 0;
                }
                // 外层循环遍历物品
                for(int i = 1;i <= N;i++){// 内层循环遍历 1~W(背包容量)
                    for(int j = 0;j <= W;j++){
                        // 外层循环 i, 如果第 i 个物品品质大于以后背包容量
                        if (wt[i] > W) {dp[i][W] = dp[i-1][W];  // 继承上一个后果
                        } else {
                            // 在“上一个后果价值”和“把以后第 i 个物品装入背包里所失去价值”二者里选价值较大的
                            dp[i][W] = Math.max(dp[i-1][W],dp[i-1][W-wt[i]] + val[i])
                        }
                    }
                }
        }
}

只有咱们定义好了 状态 （dp 数组的定义），理清了 状态之间是如何转移 的，最初的代码瓜熟蒂落。

本文所说的这个 0-1 背包问题 ，Leetcode 上并没有这个原题，所以对于背包问题，最重要的是它的 变种。

背包问题是 一大类问题 的统称，很大一部分动静布局的题深层分析都能够转换为背包问题。

所以还须要了解领会 背包问题 的核心思想，再将此种思维使用到其它 一类背包问题 的问题上。

那么背包问题还有哪些变动呢？咱们下期见～