轻松学DP——动态规划 + 0-1背包

作者：运维做开发 | 2024-07-08 14:36:35

踩

轻松学DP——动态规划 + 0-1背包

    }

    return canBreak[s.length()];

}
1
2
3
4
5

}




### []( )[LeetCode120\_三角形最小路径和]( )



![在这里插入图片描述](https://img-blog.csdnimg.cn/ce52fc86edd647919407a5487d672d26.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA6Zi_5biD772e,size_20,color_FFFFFF,t_70,g_se,x_16)  

这个问题我们来用两种方法递推：自顶向下、自底向上



开始喽~



三角形是数组形象化的表现，我们要做的是，



自顶向下：



从三角形的顶点走到底部，根据：`每一步只能移动到下一行的相邻节点(节点下标相同或者节点下标+1)`这个约束，走到底部的时候，找出一条路径最小的加和，返回这个最小和数。



这个问题的子问题要怎么来考虑的，即就是：我们的三角形有 n 层，最终也就是要从第 n 层这一层中找一个位置，从他走下来这条路径为加和最小值，全局最优解。那我们的局部最优解就可以往上那个看呀~ 第 n-1层，n-2层…第2层，当然，第 1 层只有一个数，这个数是必须要包括的。



分析完思想，我们来说做法： 定义一个和原数组大小相同的二维数组，一层一层填充这个数组，从上往下，一层一层找路走，把以上的加和放在这个位置，



状态： `F(i,j) = Math.min( F(i-1, j-1), F(i-1, j)) + triangle[i][j]`



最后就从最后一层中返回一个位置为最小和的结果就好啦~



点个赞呗~



代码：



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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

import java.util.ArrayList;

import java.util.List;

// 问题：从顶部到底部的最小路径和

// 状态定义：从(0,0)到(i,j)的最小路径和

// 状态转移方程：F(i,j)：Math.min(F(i-1,j),F(i-1,j-1)) + array[i][j]

// (j == 0 || j == i) : F(i,j)

// j == 0: F(i-1,0) + array[i][0]

// j == i: F(i-1,j-1) + array[i][j]

// 状态初始化：F(0,0) = array[0][0]

// 返回结果：Math.min(F(row-1,j)…)

public class LeetCode120_三角形最小路径和 {

public int minimumTotal(List<List<Integer>> triangle) {

    if(triangle.size() == 0 ) {

        return 0;

    }

    List<List<Integer>> minPathSum = new ArrayList<>();

    for (int i = 0; i < triangle.size(); i++) {

        minPathSum.add(new ArrayList<>());

    }

    // F[0][0]初始化

    minPathSum.get(0).add(triangle.get(0).get(0));

    for (int i = 1; i < triangle.size(); i++) {

        int curSum = 0;

        for (int j = 0; j <= i; j++) {

            if (j == 0){

                curSum = minPathSum.get(i-1).get(0);

            }else if (j == i) {

                curSum = minPathSum.get(i-1).get(j-1);

            }else {

                curSum = Math.min(minPathSum.get(i-1).get(j-1),

                        minPathSum.get(i-1).get(j));

            }

            minPathSum.get(i).add(triangle.get(i).get(j) + curSum);

        }

    }

    int size = triangle.size();

    int allMin = minPathSum.get(size-1).get(0);

    for (int i = 1; i < size; i++) {

        allMin = Math.min(allMin,minPathSum.get(size-1).get(i));

    }

    return allMin;

}
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

}




自底向上思想：这个更容易理解，看下面的注解就懂啦



1
2
3
4
5
6
7

// 自底向上

// 状态F(i,j): 从(i,j)到达最后一行的最小路径和

// 状态转移方程：

//      F(i,j): min(F(i+1,j),F(i+1, j+1)) + array[i][j]

// 初始状态：

//      F(row - 1) = array[row-1][j]

// 返回结果：

//      F(0,0)

public int minimumTotal2(int[][] triangle) {

    int row = triangle.length;

    for (int i = row-2; i >= 0 ; i--) {

        for (int j = 0; j <= i; j++) {

            triangle[i][j] = Math.min(triangle[i+1][j+1],triangle[i+1][j]) + triangle[i][j];

        }

    }

    return triangle[0][0];

}
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




> 来两道练习题巩固一下吧：  

> [LeetCode62\_不同路径]( )

> 

> [LeetCode64\_最小路径和]( )



[]( )0-1 背包问题

===========================================================================



背包问题可以通过动态规划算法来实现。



[]( )什么叫01背包问题？

-----------------------------------------------------------------------------



> 背包问题通俗的说，就是假如你⾯前有3块宝⽯分别为a, b, c, 每块宝石的重量不同，并且每块宝石所带来的价值也不同（注意：这里宝石的重量的价值没有特定关系），目前我们有⼀个背包，只有固定的容量，要解决的问题就是在⼀定容量的背包⾯前装哪几块宝⽯才能获取到最大的价值，对于每块宝石我们只有拿或者不拿这两种选择，拿为1不拿为0，因此叫做0-1背包问题。



[]( )示例

---------------------------------------------------------------------



有一个背包，其容量为 4 ，有三块宝石a，b，c，大小分别为：\[1, 4, 3\]；价值分别为：\[15, 30, 20\]，怎么装才能使得获取的价值最大？



| 宝石 | 重量 | 价值 |

| --- | --- | --- |

| A | 1 | 15 |

| B | 4 | 30 |

| C | 3 | 20 |



⾸先对于我们人去操作而言，首先考虑应该是质量最轻，并且价值最大的，从数据中我们可以看到宝石c质量最小，且价值最大，应该优先考虑装这⼀块，然后依次考虑其他的。这种方式就是考虑性价比最高的宝⽯。我们可以将这个问题进⾏简化，目前是背包承重为4，因此，我们的选择较多，不知从何下⼿，那么我们假设背包的承重为3或者是2甚至是 1。在这种情况下，我们的选择就不多了，对于人类选择也是，在选择不多的情况下更容易找出最优方案，同样计算机也是。因此我们的背包问题也是从这开始，**将选择较多的问题转化为选择不多的问题。在选择不多的情况下进行选择，有利于比较判断，依次递增，** 最后解决背包承重为11的问题。



> 我们知道：对于背包问题，其实是⼀个动态规划，对于动态规划，⼤多数都是⽤⼀个数组来进⾏保存。那么我们来试着填充一下这个数组。



| 宝石 | 0 | 重量1的价值 | 重量2的价值 | 重量3的价值 | 重量4的价值 |

| --- | --- | --- | --- | --- | --- |

|  | 0 | 0 | 0 | 0 | 0 |

| A | 0 | 15(a) | 15(a) | 15(a) | 15(a) |

| B | 0 | 15(a) | 15(a) | 15(a) | 30(取a放b) |

| C | 0 | 15(a) | 15(a) | 20(取a放c) | **35(a+c)** |



**说明：**  

i：行坐标，代表宝石  

j：列坐标，代表背包容量大小  

v\[i\]\[j\]：前 i 个宝石中能够装入容量为 j 的背包里的最大价值。



`装入顺序从上到下、从左到右`



### []( )填表过程：



1.  v\[i\]\[0\]：当容量为 0 时，价值为 0，所以这一列都为 0。

2.  v\[0\]\[j\]：不放宝石，价值为0。

3.  接下来一行一行看，对于宝石a，他在容量为1，2，3，4的情况下，都可以放入，我们在第一行表中填入宝石a的价值。

4.  再看宝石b，因为它的重量为4，所以在容量为1，2，3，的情况下它是放不下的，所以我们直接把上一行的价值拿下来，也就是此时包里装的是宝石a的价值。当容量为 4 时，可以放得下宝石b 了，但是因为包包里面此时有宝石a 占着空间，此时我们比较 \[宝石a 的价值 < 宝石b 的价值\] 就理所当然的取出a ，放入b，使价值最大。

5.  最后我们放入宝石c，因为它的重量为3，所以在容量为1，2，的情况下它是放不下的，所以我们直接把上一行的价值拿下来，也就是此时包里装的是宝石a的价值。当容量为 3 时，可以放得下宝石b 了，但是因为包包里面此时有宝石a 占着空间，此时我们比较 \[宝石a 的价值 < 宝石c 的价值\] 就理所当然的取出a ，放入c，使价值最大，到容量为 4 时，背包此时还有剩余的空间大小为 1，它可以容纳宝石a，这时自然而然把宝石a 放入，此时背包内的总价值就为 35，也是最优解。



[]( )背包问题的思路：

---------------------------------------------------------------------------



> 背包问题主要是指⼀个给定容量的背包、若干具有⼀定价值和重量的物品，如何选择物品放入背包使物品的价值最大。 这里的0-1背包是每个物品只能放一个，0→不放，1→放，求最大价值。



**利用动态规划来解决。每次遍历到的第i个物品，根据w\[i\]和v\[i\]来确定是否需要将该物品放⼊背包中。即对于给定的n个物品，设v\[i\]、w\[i\]  

分别为第i个物品的价值和重量，C为背包的容量。  

令v\[i\]\[j\]表示在前 i 个物品中能够装入容量为j的背包中的最大价值。**



可以推出：



1.  **v\[i\]\[0\] = v\[0\]\[j\] = 0** ，不放物品或者背包容量为0

2.  **当 w\[i\] > j 时 ：v\[i\]\[j\] = v\[i-1\]\[j\]** ，物品重量大于当前最大容量，价值不会增加，填表时把上一行移下来就行。

3.  **当 j > w\[i\] 时：v\[i\]\[j\] = max(v\[i-1\]\[j\]，v\[i\]+v\[i\]\[j-w\[i\]\])**，就是比较之前不装入它的价值和为了装入它取出包内其他物品后的价值再加上它的价值的大的那一个值。  

    v\[i-1\]\[j\]：就是上⼀个单元格的装入的最⼤值。  

    v\[i\]：表示当前要装⼊商品的价值。  

    v\[i-1\]\[j-w\[i\]\] ：表⽰在前 i-1 个物品中能够装入容量为 j-w\[i\] 的背包中的最大价值。



[]( )做题巩固 [九章算法LintCode125]( )

--------------------------------------------------------------------------------------------------------------------------------



![在这里插入图片描述](https://img-blog.csdnimg.cn/96c07a35b86e492e94b79e6543cde85e.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA6Zi_5biD772e,size_20,color_FFFFFF,t_70,g_se,x_16)



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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153

/**

状态F(i,j)：从前i个商品中选择，包的大小为j时的最大价值。
转移方程：
第i个商品可以放入大小为j的包中：

   F(i,j) = Math.max(F(i-1,j) + V(i-1), F(i-1,j-A[i-1]) + V(i-1))
1

        // F(i-1,j): 表示不把第i个物品放入背包中， 所以它的价值就是前i-1个物品放入大小为j的背包的最大价值
1

        // F(i-1, j - A[i]) + V[i]：表示把第i个物品放入背包中，价值增加V[i],但是需要腾出A[i-1]的大小放第i个商品
1

```
        // 这里由于下标会
1
```
```
   F(i,j) = F(i-1,j)
1
```
初始状态：

    F(i,0) = 0  包空间为0，放不下，价值为0
1

    F(0,j) = 0  没有物品，没有价值
1

返回值：F(n,m)

public class LintCode125_背包问题 {

public int backPackII(int m, int[] A, int[] V) {

    // write your code here

    int n = A.length;

    int[][] maxValue = new int[n+1][m+1];



    for (int i = 1; i <= n; i++) {

        for (int j = 1; j <= m; j++) {

            if(A[i-1] <= j) {

                maxValue[i][j] = Math.max(maxValue[i-1][j],
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

一线互联网大厂Java核心面试题库

正逢面试跳槽季，给大家整理了大厂问到的一些面试真题，由于文章长度限制，只给大家展示了部分题目，更多Java基础、异常、集合、并发编程、JVM、Spring全家桶、MyBatis、Redis、数据库、中间件MQ、Dubbo、Linux、Tomcat、ZooKeeper、Netty等等已整理上传，感兴趣的朋友可以看看支持一波！

or (int i = 1; i <= n; i++) {

        for (int j = 1; j <= m; j++) {

            if(A[i-1] <= j) {

                maxValue[i][j] = Math.max(maxValue[i-1][j],
1
2
3
4
5

一线互联网大厂Java核心面试题库

[外链图片转存中…(img-bbLlJelv-1714805666578)]

本文已被CODING开源项目：【一线大厂Java面试题解析+核心总结学习笔记+最新讲解视频+实战项目源码】收录

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/运维做开发/article/detail/799039