Java 与 C++ 之间有一堵由内存动态分配和垃圾收集技术所围成的“高墙”，墙外面的人想进去，墙里面的人却想出来。

运行时数据区域

Java 虚拟机在执行 Java 程序的过程中会把它所管理的内存划分为若干个不同的数据区域。根据《Java 虚拟机规范（Java SE 7 版）》的规定，包括如下几个运行时数据区域，如图：

程序计数器

程序计数器是一块较小的内存空间，它可以看作是当前线程所执行的字节码的行号指示器。

由于 Java 虚拟机的多线程是通过 线程轮流切换并分配处理器执行时间的方式来实现的，在任何一个确定的时刻，一个处理器（对于多核处理器来说是一个内核）都只会执行一条线程中的指令。因此，为了线程切换后能恢复到正确的执行位置，每条线程都需要有一个独立的程序计数器，各条线程之间计数器互不影响，独立存储，这类内存区域称为“线程私有”的内存。

• 线程正在执行的是一个 Java 方法，这个计数器记录的是正在执行的虚拟机字节码指令的地址；
• 线程正在执行的是一个 Native 方法，这个计数器值则为空（Undefined）。

此内存区域是唯一一个在 Java 虚拟机规范中没有规定任何 OutOfMemoryError 情况的区域。

Java 虚拟机栈

与程序计数器一样它也是线程私有的，它的生命周期与线程相同。虚拟机栈描述的是 Java 方法执行的内存模型：每个方法在执行的同时都会创建一个栈帧用于存储局部变量表、操作数栈、动态链接、方法出口等信息。每一个方法从调用直至执行完成的过程，就对应着一个栈帧在虚拟机栈中入栈到出栈的过程。

在 Java 虚拟机规范中，对这个区域规定了两种异常状况：

• 如果线程请求的栈深度大于虚拟机所允许的深度，将抛出 StackOverflowError 异常；
• 如果虚拟机栈可以动态扩展，如果扩展时无法申请到足够的内存，就会抛出 OutOfMemoryError 异常。

本地方法栈

本地方法栈与虚拟机栈所发挥的作用是非常相似的，它们之间的区别不过是 虚拟机栈为虚拟机执行 Java 方法（也就是字节码）服务，而本地方法栈则为虚拟机使用到的 Native 方法服务。

Java 堆

Java 堆是被所有线程共享的一块内存区域，在虚拟机启动时创建。

此内存区域的唯一目的就是存放对象实例，几乎所有的对象实例都在这里分配内存。Java 虚拟机规范中的描述是：所有的对象实例以及数组都要在堆上分配。

但是随着 JIT 编译器的发展与逃逸分析技术逐渐成熟，栈上分配、标量替换优化技术将会导致一些微妙的变化发生，所有的对象都分配在堆上也渐渐变得不是那么“绝对”了。

Java 堆是垃圾收集器管理的主要区域，所以有时也称之为“GC 堆”。

• 内存回收角度看，它可以细分为新生代和老年代，细致一点可以分为 Eden 空间、From Survivor 空间、To Survivor 空间等。
• 内存分配角度看，它可能划分出多个线程私有的分配缓冲区。

方法区

方法区与 Java 堆一样，是各个线程共享的内存区域，它用于存储已被虚拟机加载的类信息、常量、静态变量、即时编译器编译后的代码等数据。

Java 虚拟机规范对方法区的限制非常宽松，除了和 Java 堆一样不需要连续的内存和可以选择固定大小或者可扩展外，还可以选择不实现垃圾收集。

根据 Java 虚拟机规范的规定，当方法区无法满足内存分配需求时，将抛出 OutOfMemoryError 异常。

运行时常量池

运行时常量池是方法区的一部分。它相对于 Class 文件常量池的一个重要特征是 具备动态性，Java 语言并不要求常量一定只有编译期才能产生，也就是并非预置入 Class 文件中常量池的内容才能进入方法区运行时常量池，运行期间也可能将新的常量放入池中，这种特性被开发人员利用得比较多的便是 String 类的 intern() 方法。

当常量池无法再申请到内存时会抛出 OutOfMemoryError 异常。

直接内存

直接内存并不是虚拟机运行时数据区的一部分，也不是 Java 虚拟机规范中定义的内存区域。但是这部分内存也被频繁地使用，而且也可能导致 OutOfMemoryError 异常出现。

在 JDK 1.4 中新加入了 NIO（New Input/Output）类，引入了一种基于通道（Channel）与缓冲区（Buffer）的 I/O 方式，它可以使用 Native 函数库 直接分配堆外内存，然后通过一个存储在 Java 堆中的 DirectByteBuffer 对象作为这块内存的引用进行操作。这样能在一些场景中显著提高性能，因为避免了在 Java 堆和 Native 堆中来回复制数据。

HotSpot 虚拟机对象探秘

以常用的虚拟机 HotSpot 和常用的内存区域 Java 堆为例，博主也在此简短总结下 HotSpot 虚拟机在 Java 堆中对象分配、布局和访问的全过程。

对象的创建

虚拟机遇到一条 new 指令时，首先将去检查这个指令的参数是否能在常量池中定位到一个类的符号引用，并且检查这个符号引用代表的类是否已被加载、解析和初始化过。如果没有，那必须先执行相应的类加载过程。（类加载过程之后的博文会有相关总结）

在类加载检查通过后，接下来虚拟机将为新生对象分配内存。内存分配有两种方式：

• 假设 Java 堆中内存是绝对规整的，所有用过的内存都放在一边，空闲的内存放在另一边，中间放着一个指针作为分界点的指示器，那所分配内存就仅仅是把那个指针向空闲空间那边挪动一段与对象大小相等的距离，这种分配方式称为“指针碰撞”。
• 如果 Java 堆中内存并不是规整的，已使用的内存和空闲的内存相互交错，那就没有办法简单地进行指针碰撞了，虚拟机就必须维护一个 列表，记录上哪些内存块是可用的，在分配的时候从列表中找到一块足够大的空间划分给对象实例，并更新列表上的记录，这种分配方式称为“空闲列表”。

选择哪种分配方式由 Java 堆是否规整决定，而 Java 堆是否规整又由所采用的垃圾收集器是否带有 压缩整理功能决定。

对象的内存布局

在 HotSpot 虚拟机中，对象在内存中存储的布局可以分为 3 块区域：对象头、实例数据和对齐填充。

对象头包括两部分信息：

• 第一部分用于存储对象自身的运行时数据，如哈希码、GC 分代年龄、锁状态标志、线程持有的锁、偏向线程 ID、偏向时间戳等；
• 另一部分是类型指针，即对象指向它的类元数据的指针，虚拟机通过这个指针来确定这个对象是哪个类的实例。

并不是所有的虚拟机实现都必须在对象数据上保留类型指针，也就是说查找对象的元数据信息并不一定要经过对象本身。

如果对象是一个 Java 数组，那在对象头中还必须有一块用于记录数组长度的数据，因为虚拟机可以通过普通 Java 对象的元数据信息确定 Java 对象的大小，但是从数组的元数据中却无法确定数组的大小。

实例数据部分是对象真正存储的有效信息，也是在程序代码中所定义的各种类型的字段内容。

对其填充并不是必然存在的，也没有特别的含义，它仅仅起着占位符的作用。

对象的访问定位

对象访问方式取决于虚拟机实现而定的，目前主流的访问方式有 使用句柄和 直接指针两种。

• 如果使用句柄访问的话，那么 Java 堆中将会划分出一块内存来作为句柄池，reference 中存储的就是对象的句柄地址，而句柄中包含了对象实例数据与类型数据各自的具体地址信息。
• 如果使用直接指针访问，那么 Java 堆对象的布局中就必须考虑如何放置访问类型数据的相关信息，而 reference 中存储的直接就是对象地址。

这两种对象访问方式各有优势。

使用句柄来访问的最大好处就是 reference 中存储的是稳定的句柄地址，在对象被移动时只会改变句柄中的实例数据指针，而 reference 本身不需要修改；

使用直接指针访问方式的最大好处就是速度更快，它节省了一次指针定位的时间开销。

潜意识还没养成的我在思考问题方面总会出点岔子，老是走一些弯路。虽说结果可能是一样的，过程却是复杂许多，这也是我为什么决定要好好刷一遍 leetcode 中的题目的原因。数学就在于简单之美，一些看似异常复杂的问题可以巧妙地通过分治从而完美解决，很能锻炼人的逻辑思维能力，这也是我想要的。

下面来看问题的描述：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

示例 1:

输入: ["flower","flow","flight"]
输出: "fl"
示例 2:

输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。
说明:

所有输入只包含小写字母 a-z 。

问题看似很简单，查找字符串数组中每个元素的最长公共前缀。

确实简单，我这个莽夫的第一想法就是遍历暴力分析。两个循环能解决，问题是不大，但是很不优雅，看着就难受。

虽说“黑猫白猫，能抓老鼠的就是好猫”，但是两猫都能抓老鼠，那我当然还是喜欢高颜值猫了！

随后我就去官网找到了我要的答案：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

/**
 * 官网解法
 * 
 * @param strs
 * @return
 */
public static String longestCommonPrefix1(String[] strs) {
    if (strs.length == 0)
        return "";
    String prefix = strs[0]; // 以第一个字符串为基准
    for (int i = 1; i < strs.length; i++)
        while (strs[i].indexOf(prefix) != 0) { // 依次找到均满足的相同起始字符
            prefix = prefix.substring(0, prefix.length() - 1);
            if (prefix.isEmpty())
                return "";
        }
    return prefix;
}

这一种是我觉得最好理解最满意的一种解法。

这里以第一个元素为基准值，挨个与其它元素进行比较。while 循环里面就是为了使基准值成为比较元素的起始字符串，故它不满足就每次截掉最后一位。若是全部截完了那就是无公共前缀了。

这完美体现了分而治之，将所有元素的比较变成了两个元素之间的比较，可以节省其运行时间同时也使得代码更好理解更加优雅。

学习了，牢记。

LeetCode 中有多道组合总和（Combination Sum）的题，这些题目都是比较经典的，面试很可能会问到。我这一想，还真是。今天就来简单总结下这一系列题目，总结很重要，还要时而回顾！

Combination Sum I

第一道题的描述如下：

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

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明：

所有数字（包括 target）都是正整数。
解集不能包含重复的组合。 
示例 1:

输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
  [7],
  [2,2,3]
]
示例 2:

输入: candidates = [2,3,5], target = 8,
所求解集为:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

注意点：

• candidates 中的数字可以无限制重复被选取。
• 解集不能包含重复的组合。

这时候头脑里很快就会产生一个思路：无限遍历该数组，直到其元素之和满足条件，然后塞入集合中。

这个想法没问题，不过在这过程中我们怎么才能满足解集不能包含重复的组合。这个条件呢？

对对对，那就是确定一个 index，我们要保证数组不往回找就是了。

解题代码如下：

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

public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> list = new ArrayList<>();
        Arrays.sort(candidates);
        recursive(list, new ArrayList<>(), candidates, target, 0);
        return list;
    }

    /**
     * 
     * @param list
     *            总的输出 list
     * @param tempList
     *            存放的 list
     * @param nums
     *            数组
     * @param remain
     *            剩余值
     * @param index
     *            数组下标
     */
    private void recursive(List<List<Integer>> list, List<Integer> tempList, int[] nums, int remain, int index) {

        if (remain < 0) // return 或者进行 add 操作后就开始执行弹出尾部元素 塞入下个元素
            return;
        else if (remain == 0)
            list.add(new ArrayList<>(tempList)); // 这里需要注意不能直接 list.add(tempList),最终 tempList 所指向的对象是空的,
                                                    // 所以需要 new 一个新对象，将值复制进去
        else {
            for (int i = index; i < nums.length; i++) {
                tempList.add(nums[i]); // 挨个塞入
                recursive(list, tempList, nums, remain - nums[i], i); // 由于元素可重复 所以是 i
                tempList.remove(tempList.size() - 1); // 挨个弹出
            }
        }
    }

我这注释什么的都有，理解起来不成问题吧。这里需要注意的就是两个点：list.add(new ArrayList<>(tempList)); 和 recursive(list, tempList, nums, remain - nums[i], i);。

这里先对数组进行排序可以使计算更快，当然你也可以不排序。

Combination Sum II

第二道对第一道稍微加工了一下，描述如下：

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

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

说明：

所有数字（包括目标数）都是正整数。
解集不能包含重复的组合。 
示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]
示例 2:

输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
  [1,2,2],
  [5]
]

注意点：

• candidates 中的每个数字在每个组合中只能使用一次。
• 解集不能包含重复的组合。

是的，这里把条件改了，数组中的每个元素在每个组合中只能使用一次！

这就意味着每次递归操作时其下标都需要往后移一位了！

代码如下：

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

public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> list = new ArrayList<>();
        Arrays.sort(candidates);
        recursive(list, new ArrayList<>(), candidates, target, 0);
        return list;

    }

    /**
     * DFS 添加每个满足条件的集合
     * 
     * @param list
     *            最终返回集合
     * @param tempList
     *            每个满足条件的子集合
     * @param candidates
     *            数组
     * @param remain
     *            剩余值
     * @param index
     *            数组下标
     */
    private void recursive(List<List<Integer>> list, List<Integer> tempList, int[] candidates, int remain, int index) {
        if (remain < 0)
            return;
        else if (remain == 0)
            list.add(new ArrayList<>(tempList));
        else {
            for (int i = index; i < candidates.length; i++) {
                if (i > index && candidates[i] == candidates[i - 1]) // 说明两个值相等且之前一个值已经返回
                    continue;
                tempList.add(candidates[i]);
                recursive(list, tempList, candidates, remain - candidates[i], i + 1); // 规定数组中每个数字在每个组合中只能使用一次
                tempList.remove(tempList.size() - 1);
            }
        }
    }

相比较上一题的代码，这次只是加了一个条件判断以及递归中元素下标加了一。

这里就要对数组先进行排序操作了，新增的条件判断也是为了优化代码执行速度。

Combination Sum III

再来看第三道变形，描述如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。

说明：

所有数字都是正整数。
解集不能包含重复的组合。 
示例 1:

输入: k = 3, n = 7
输出: [[1,2,4]]
示例 2:

输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]

这次不给出数组了，而是规定了数组中元素的取值范围。

双手一摊，这还不是一样吗，不给我就自己造就是了！

注意点：

• 解集不能包含重复的组合。

解题代码如下：

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

public List<List<Integer>> combinationSum3(int k, int n) {
        int[] nums = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
        List<List<Integer>> list = new ArrayList<>();
        dfs(list, new ArrayList<>(), nums, k, n, 0);
        return list;

    }

    /**
     * 
     * @param list
     *            最终返回的 list
     * @param tempList
     *            作为寻求满足条件的暂存 list
     * @param nums
     *            数组
     * @param reNum
     *            剩余的元素个数
     * @param reSum
     *            剩余的总和
     * @param index
     *            数组下标
     */
    private void dfs(List<List<Integer>> list, List<Integer> tempList, int[] nums, int reNum, int reSum, int index) {
        if (reNum < 0 || reSum < 0) // 两者有其一小于 0 就是不满足条件
            return;
        if (reNum == 0 && reSum == 0) // 两者都为 0 时满足条件，塞入
            list.add(new ArrayList<>(tempList));
        else if (reNum == 0 || reSum == 0) // 两者中有且只有一者等于 0 就不满足条件
            return;
        else {
            for (int i = index; i < nums.length; i++) {
                tempList.add(nums[i]);
                dfs(list, tempList, nums, reNum - 1, reSum - nums[i], i + 1); // 不能重复元素 所以 i + 1
                tempList.remove(tempList.size() - 1);
            }
        }
    }

真不愧为机智小少年……

Combination Sum IV

第四道变形就复杂了一些了，描述如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。

示例:

nums = [1, 2, 3]
target = 4

所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

请注意，顺序不同的序列被视作不同的组合。

因此输出为 7。

这里数组的元素可以重复，且组合的元素也能相同，但是顺序要不同。

一开始当然就是无脑循环了，然后满足条件就加上一，结果就是超时……

说明这么暴力不行的……

后来一想，无脑循环就相当于每一次都从头进行循环算了一遍，很多都是重复的计算。

对了，DP 浮现在了脑中，在那飘啊飘。

代码如下：

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

private int[] dp;

    /**
     * DP
     * 
     * @param nums
     * @param target
     * @return
     */
    public int combinationSum4(int[] nums, int target) {
        dp = new int[target + 1];
        Arrays.fill(dp, -1);
        dp[0] = 1;
        return helper(nums, target);
    }

    private int helper(int[] nums, int target) {
        if (dp[target] != -1) {
            return dp[target]; // 若是之前的已经计算过了 直接返回
        }
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            if (target >= nums[i]) { // 所有组合的种数相加
                res += helper(nums, target - nums[i]);
            }
        }
        dp[target] = res; // 计算后赋值用于之后的数字使用
        return res;
    }

用空间换取时间的操作，DP + 递归稍微费点脑。

还有一种解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

/**
     * DP
     * 
     * @param nums
     * @param target
     * @return
     */
    public int combinationSum4(int[] nums, int target) {
        int[] comb = new int[target + 1];
        comb[0] = 1;
        for (int i = 1; i < comb.length; i++) {
            for (int j = 0; j < nums.length; j++) {
                if (i - nums[j] >= 0) {
                    comb[i] += comb[i - nums[j]];
                }
            }
        }
        return comb[target];
    }

好了，组合总和系列（Combination Sum）的题目总结完了。记住了回溯。

使用 ssh 反向隧道穿透 NAT 访问内网主机

前言

由于公司经常会有项目需要去业主那边搭建服务器，基本不需要什么流量所以就准备用 4G 网卡搭建。而该网卡无固定公网 ip，只有内网 ip，我们目的就是为了可以远程操控以避免有时因业务需要往业主那边跑，要是地方比较远来回一趟也得花个把星期，不划算。所以就研究了下 ssh 隧道穿透来满足我们的需求。

场景

现在我们有三台机子：

• A：公司内网电脑（Win 10）
• B：公司内网服务器（Linux，固定外网 ip：58.247.33.44，ssh 开放端口：8862）
• C：业主那边 4G 网卡搭建的服务器（Linux，无固定外网 ip，ssh 开放端口：22）

操作前：A 可以访问 B，C 能上网也能访问 B，但是 B 不能访问 C，A 不能访问 C
我们需要满足：A 可以访问 C

当然，很多远程桌面软件可以满足我们这个需求，但是由于太不方便和不稳定，还是考虑 ssh。（安装 ssh 可见底文的附加安装指令）

配置

配置 B 服务器

• 修改服务器上的 sshd 设置

vim /etc/ssh/shhd_config 建议使用 vim，vim 比 vi 更强大（安装 vim 可见底文的附加安装指令）

• 把 GatewayPorts 打开(去掉前面的 # 号注释，没有就直接在底下添加)

GatewayPorts yes 打开允许映射端口

• 存盘后退出，并重新启动 sshd (不知如何操作文件的自行上网查阅)

service ssh restart 这个具体得看你 service 的实际名字（Ubuntu 下 service --status-all 可以查看所有服务状态）

配置 C 服务器

可以进行映射操作了

ssh -NfR 1234:localhost:22 user@58.247.33.44 -p8862

N 参数，表示只连接远程主机，不打开远程shell。

f 参数，表示后台运行。

R 参数接受三个值，分别是”远程主机端口:目标主机:目标主机端口”。

p 参数，表示指定 ssh 对外开放的端口号。

user 是 B 服务器的用户。

这条命令的意思，就是让 B 服务器监听它自己的 1234 端口，然后将所有数据经由 B 服务器转发到 C 服务器的 22 端口。这就被称为”远程端口绑定”。

这里每次连接需要输入 B 服务器的密码，不太方便，待会再详细介绍。

映射操作后我们可以发现在 B 服务器上已经开启了 1234 端口的监听，已经可以通过 1234 端口进行 ssh 连接到 C 服务器了。

密钥验证，直接登录

接回上面说的每次需要输入密码的问题，我们可以用 ssh 密钥来实现自动登录。

在 C 服务器上生成公钥和私钥

ssh-keygen （一直 enter）

ls ~ /.ssh/ 查看是否生成，显示如下

id_rsa id_rsa.pub known_hosts

ssh-copy-id user@58.247.33.44 复制到 B 服务器中

好了，这样就不需要每次都输入 B 服务器密码了。

autossh 实现自动重连

由于上述的 ssh 反向连接十分不稳定，可能随时断开，一旦断开就无法进行访问了。所以我们需要 autossh，它可以实现自动重连。（安装 autossh 可见底文的附加安装指令）

autossh -M 5678 -NR 1234:localhost:22 user@58.247.33.44 -p8862

M 参数，指定了 autossh 的监听端口，监听是否断开然后进行重连操作

autossh 本身就是后台执行，所以就省去了 f 参数。

到这里就很完美了，可是还不够。要是 C 服务器宕机重启了怎么办，autossh 又不会自动执行。

实现开机自启

这里以 Ubuntu 18.04 为例。

ls /lib/systemd/system 执行该指令我们可以看到许多启动脚本，我们需要操作的就是 rc.local.service

打开脚本内容，我们在最后面加上一段：

1
2
3

[Install]  
WantedBy=multi-user.target  
Alias=rc-local.service

保存退出。

由于 ubuntu-18.04 默认是没有 /etc/rc.local 这个文件的，需要自己创建。

1
2

sudo touch /etc/rc.local
chmod 755 /etc/rc.local

这里千万别忘记给 rc.local 文件设置可执行权限，不然没用。

在 rc.local 中你就可以编写脚本了。注意开头 #!/bin/bash 不可少

例如我的是：

1
2
3
4

#!/bin/bash
LOG_TIME=`date "+%Y-%m-%d %H:%M:%S"`
echo '123456' | sudo -S autossh -M 5678 -NR 1234:localhost:2223 user@58.247.33.44 -p8862
echo "autossh restart:"$LOG_TIME >>/usr/local/autossh.log

这里我是用 root 权限执行，123456 是 C 服务器的用户密码。 >> 表示追加，不覆盖。同时打印了执行的时间。

最后一步，前面我们说 systemd 默认读取 /etc/systemd/system 下的配置文件, 所以还需要在 /etc/systemd/system 目录下创建软链接。

ln -s /lib/systemd/system/rc.local.service /etc/systemd/system/

可以了，重启系统查看脚本是否执行，日志中是否有内容。

参考博文

笔者参考了如下博文并进行了整理实验：

• 使用ssh隧道穿透NAT访问内网主机(超干货)
• SSH反向连接及Autossh
• ubuntu-18.04 设置开机启动脚本
• ubuntu 18.04 配置 rc.local

附加安装

• 更新源列表

sudo apt-get update

• 安装 ssh

sudo apt-get install openssh-client 安装客户端 （反向隧道需要）

sudo apt-get install openssh-server 安装服务端

• 安装 vim

1
2

sudo apt-get remove vim-common
sudo apt-get install vim

Ubuntu 18.04 中 vi 方向键有点问题，vim 很好用。

• 安装 autossh

sudo apt-get install autossh

• 安装 net-tools

当发现输入 ifconfig 不可用时

sudo apt install net-tools 装之

近些日子里差不多都在看《三体》，专业书籍都抛到脑后了，甚是着迷。

《三体》中每本序言都说了“基石”二字。刘慈欣先生真是可谓中国科幻届领军人物！其脑洞之大，学术之广，思维之严谨。书中大量出现了数学、物理等知识，众多专业术语，还将中外古今大多名人汇聚一起，展开“搏斗”，来回穿梭于时光长廊。

这几周每每到了周末，我便早上泡了杯麦片弄了点简易早餐（就是搞了个手抓饼），吃完躺床上稍稍休整便开始动手收拾《三体》世界，奔向不远的城建职业学院中去。到了那差不多十一点半，便顺道去了其食堂解决了中午伙食，这学校看上去有点年代的样子，环境倒是还不错就是人不多。吃完我就去图书馆里找了个位置开始翻起来。

当我一开始看的时候我就想起来了前几年看过的那本《天才在左，疯子在右》。其中有个微观故事我印象十分深刻，大致讲的是有个人不停洗澡洗手，洗到脱皮还是要洗，他说要把身上的细菌洗掉，细菌占领了我们，我们的世界其实是在它们的控制之下。是啊，生活中到处都是它们，我们处处被监视，自以为是的我们又怎么会知道它们到底是个什么样的存在。

自以为历尽沧桑，其实刚蹒跚学步，自以为掌握了竞争的秘密，其实远没有竞争的资格。

• 射手假说：有一名神枪手，在一个靶子上，每隔10cm打出一个洞。设想这个靶子上生活着一种二维智能生物，它们中的科学家在对自己的宇宙进行观察后，发现了一个伟大的定律：每隔 10cm 单位，必然会有一个洞。 它们把这个神枪手一时兴起的随意行为，看成自己宇宙中的铁律。

• 农场主假说：一个农场里有一群火鸡，农场主每天上午11点来给它们喂食。火鸡中的一名科学家观察这个现象，一直观察了近一年都没有出现例外，于是它也发现了自己宇宙中的伟大定律：每天早上 11 点，就有食物降临。 它在感恩节早晨向大家宣布了这个定律，但这天早上 11 点食物没有降临，农场主进来把他们都捉去杀了。

给时光以生命，给岁月以文明。

…

将人类这种生物剖析得连骨头渣子都不剩，大量反映了人性的情节。我试想，倘若真有朝一日三体人入侵地球，地球上会不会出现极权只需五秒钟的情况。不敢想，真的可怕，越想越可怕。我们都是虫子，不敢仰望星空。

看完《三体》后整个人精神状况都不好了，本来就是有点悲观主义思维，现在却像打上了思想烙印，觉得这世界随时都会爆炸。。

不过常看看这类书籍对我们还是很有好处的。码农，不就需要思维发散，眼界开阔，炸开世界视角。这能使我们想的更多，头脑更加灵活，逻辑能力自然也就上去了，看得还是很爽的。何况，刘慈欣先生怎么说也算是同行啊，要向先生看齐！

成功者有个特点，他们都具有前沿的思维，能够灵敏地感知未来的变化并能很快去拥抱现实。刘老在 06 年便能在脑中浮现如此气势磅礴的场景，读完作品我真是深深被其折服了。以后的日子里还需要再锻炼触觉，开阔视野，发散思维，并在实际生活中能应用自如，走向成功之路！

期待三体电影~

今早著名主持人李咏抗癌去世的消息出现在了大众面前，曾经站在台上“我是李咏，我们下期再见！”的声音虽然已经很久没有听到，但也算是从小看着他的节目长大。现在我们长大了，他却不见了。生命真的很脆弱，不由得又想起了《三体》中多次爆发的伤亡场景。

听我姑父说我爷爷是前列腺癌去世的。这种癌症遗传率很高，不知道我会不会中招，惨兮兮。冬眠技术啥时候能普及啊，我要冬眠，我要去未来看看人还是不是人。

前言

今天又想起来了这个问题，之前最开始是在其他论坛中看到有人说起了这个面试题。

当时只是翻了下，大致了解了如何判断链表中是否有闭环，用两个快慢指针解决，但是没有了解如何去找到闭环开始的节点。

刚上网搜了下，一群垃圾博主乱七八糟胡说八道，就知道从其他地方复制粘贴，都不过脑子的。谁说较快指针一定就是第二次在环上移动就能遇到较慢指针的，我这么个渣渣都能一眼看出来毛病一群人还复制粘贴都说 2，你们还真是 2！

问题描述

一条链表如何判断是否有环？若是有环那怎么找到链表环的入口？

解决思路

• 先判断是否有环

思路：用快慢两个指针分别从链表头开始，慢指针 -> next，快指针 -> next -> next，这样如果有环那快指针务必会跑到慢指针后面，随即两者之间的距离一次会缩小一步，最终相遇。若是未相遇且快指针的 next 为 null，则说明链表无环。

• 若是有环怎么找到环入口

链表中有闭环即快慢两指针相遇了，见下方的手工图：

一切清晰明了。让我们再来捋一捋。

当两指针在 P 点相遇，我们可列出如下等式：

1
2
3
4

2(L+x) = L+x+n*H        (n >= 1) // n 为快指针在闭环上的圈数
=> 2L+2x = L+x+n*H      (n >= 1)
=> L = n*H-x            (n >= 1)
=> L = n*(H-x)+(n-1)x   (n >= 1)

到这里，是不是有种扒光了的快感，哈哈。
网上许多博客就是把 n 默认当成了 1，实则不然。

思路：故我们可以这样做，当 l1 与 l2 相遇时，再来一个 l3 指针从链表头开始，而 l1 继续走，l2 就可以终结其使命没必要继续走了。此时 l1 和 l3 指针都是指向其 next。当 l3 指针到达环入口时，l1 也必然到达了环入口，即 l1 和 l3 指针会在环入口相遇，从而可求得入口位置。

参考博客

• 《编程之美》3.6判断链表是否相交之扩展：链表找环方法证明
• 程序员编程艺术：第九章、闲话链表追赶问题

今天总结一下二分搜索。假设这里的数组已经是升序排序好了的。

我们知道二分搜索的效率很高，它充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用 O(log n) 完成搜索任务。它的基本思想：将 n 个元素分成个数大致相同的两半，取 a[n/2] 与需要查找的目标值 x 作比较，如果 x=a[n/2] 则找到 x，算法运算终止。详情可跳转百度百科。

• 我们通常最基本的二分搜索是这样实现的(Java):

  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

  /** * 二分搜索 * * @param arr * 已升序排序数组 * @param key * 目标查找值 * @return */ public static int commonBinarySearch(int[] arr, int key) { int low = 0; int high = arr.length - 1; int middle = 0; // 定义middle if (key < arr[low] || key > arr[high] || low > high) { return -1; } while (low <= high) { middle = (low + high) / 2; if (arr[middle] > key) { // 比关键字大则关键字在左区域 high = middle - 1; } else if (arr[middle] < key) { // 比关键字小则关键字在右区域 low = middle + 1; } else { return middle; } } return -1; // 未找到结果，返回-1 }

  若是数组中存在搜索目标元素，则只要查找到任意一个便会返回该值；若是没有找到即返回 -1。

• 来看下一种，只返回目标元素第一次出现的位置下标(伪代码):

  1 2 3 4 5 6 7 8 9 10

  l = -1; u = n while l+1 != u m = (l + u) / 2 if x[m] < t l = m else u = m p = u if p >= n || x[p] != t p = -1

  n 为数组的长度，p 就是最终我们需要的下标。若是 while 循环出来的最终结果 u >= n （其实最大也只会等于 n）或者 x[u] != t（t 为我们的目标元素），那么也就是无结果，返回 -1。

• 我们再来看最后一个 function(该方法参数不同使得结果可以返回元素第一个出现的下标或者最后一个下标，也是 Java):

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

  /** * * @param nums * 已经升序排序好的数组 * @param target * 搜索目标元素 * @param left * 是否是查找第一个元素下标。true:查找目标元素第一个出现下标, false:查找目标元素最后一个出现下标 * @return */ private int extremeInsertionIndex(int[] nums, int target, boolean left) { int lo = 0; int hi = nums.length; while (lo < hi) { int mid = (lo + hi) / 2; if (nums[mid] > target || (left && target == nums[mid])) { hi = mid; } else { lo = mid + 1; } } return lo; }

  目标元素出现的第一个下标：int leftIdx = extremeInsertionIndex(nums, target, true);
  
  目标元素出现的最后一个下标：int rightIdx = extremeInsertionIndex(nums, target, false) - 1;这里需要减一，需要注意。

总结一下：二分搜索只需要注意它的边界值，原先的数组下标范围是 [0..n-1]，当你用 lo = 0, hi = n-1 去运行时，对应条件满足情况下值的赋值应该是 lo = mid + 1, hi = mid - 1；而若是用 lo = -1, hi = n 去作为条件运行时，对应条件满足情况下值的赋值就应该为 lo = mid, hi = mid，因为它两个值都是作为边界值。[0, n]、[-1, n-1]也是如此。

相关链接：

• 编程珠玑（第二版）第四章习题
• LeetCode - Find First and Last Position of Element in Sorted Array

近几日天愈发见凉，夜晚也裸睡不得了。

这帮人，唉。步入社会后确实大家之间的联系会越来越少，有这个心境，时间上也不允许啊，都得赚钱吃饭没办法……

本来是原先计划五人中秋一同去重庆耍几天。可奈何机票小贵，下不了这个手，何况有人明年还准备在苏州买婚房了，攒钱中，羡慕。后，众人纷纷拿不准放松地点，最终决定周边自驾游，先去杭州再去横店，这是计划。

什么！？女朋友亲戚忌日周年？还有这种事情的？何况婚都还没接呢，这就得过去，还是个大事。对了，就是明年准备在苏州买婚房那位，然后就五人缺席一人，计划照旧。

提前一个月我就买好了来回车票，就等那天放飞了，一年到头没有个生活，唉，哭唧唧。

什么！？临时上头派你去大连出差？还有这种事情的？连中秋都在大连过，我的乖乖宝贝啊。

又缺一人，剩三人。谁玩球谁玩！遂，计划猝！

车票退回，亏几十手续费。特么还买了张杭州博览会的门票，二十，也废了。哭唧唧。

临时决定还是回家吧，买了 22 号下午的票，24 号上午回来。哭唧唧。

不说那些伤心事了。

最近欧皇啊，豆瓣上海观影活动中连抽中了两次。

• 第一次是《悲伤逆流成河》（不是郭敬明导的），讲的是校园暴力的。我没有看过小说原著，不过说实在的郭敬明骂声很多，但是他的书看的人还不少，至少我这个年龄层次的，挺多，小女生就喜欢看这些。电影看完后感触也是有的，反映了很多人性的东西，电影全程看完也没有睡意，我比较幸运从小也没有经历过那些校园暴力，最多也就只是一些小朋友之间的矛盾。看完之后我在想，那些真实世界里经历过校园暴力的人的身心会怎么样，他们可能那时候小也许没有想那么多，但是等到长大了，懂事后，回头想起那段时间，会是个什么样的心情。电影放完之后还来了两电影中新人演员，都很年轻，演技虽然青涩也是可认可的，其中主演的演技真的很用力，感染力很强！

我说来个中间点的位置，结果给我来了张最后排的还是个角落。。

• 然后昨天去看的《李茶的姑妈》，开心麻花出品国产喜剧。这个赞！国产喜剧除了星爷很少能让观众全场一直笑到最后的，我也是笑出了声，边上那些女孩子就更别说了，猪声……支持国产喜剧，看好开心麻花！没拍图片，也是做了个角落不过还好，不是最后排了。（卢靖姗身材真棒！！真喜欢这种健康的身材）

本来是计划中秋去放飞顺道回趟家，然后国庆宅出租房七天领悟自然真理。

现在变成了中秋回家，国庆回家。也好，趁着假期在家多呆呆，山美水清环境好（家附近在通国道，环境其实破坏了很多啊）。

我姐中秋把一个男的叫到家里来吃了个饭，通过相亲认识的，这还是第一个来家里吃饭的，不知道能不能成。人嘛看上去还行，就这样看吧，老姐也是要奔三了。至于我嘛，现在只想躺在床上顺道还把钱给赚了。婚姻这事，看缘分吗？

又跟家里聊了下，爸妈都是普通农民，辛苦一辈子把我和我姐拉扯大又盖了个新房，已经是很了不起了。现在就是家里种着几亩葡萄，收获季节比较忙。等到我要结婚买房了也不能太指望家里，毕竟他们二老还要养老的，需要备点钱，虽然以后每月都有养老金。

现在是这么想的，先在上海再打拼几年，能多赚点钱就赚，当然身体还是继续要锻炼的。看以后缘分有没有，如果缘分来了，购房资格有了，手上又能够勉强付得起个首付了，那就没准要扎根上海了。不过这还太遥远了。

今天真是厉害了，骑个自行车被交警拦下来记录信息警告了。。

说下次再抓到就要罚款 50 块了，运气不好运气不好，也是我的第一次了。

以后骑车得小心了，负责的交警也是好的，确实随着共享单车出现这个自行车越来越难管理了。大城市是得好好整顿整顿。

我就是对未知的特别感兴趣，什么都想了解下，也特别喜欢扩宽自己的眼界。世界变化太快，生活中也经常时不时会触及到不同的领域，俗话说技多不压身，多学学总没错。但也说要专精。我个人是觉得，眼界是一定要不断扩宽，不能做一只井底之蛙。在领域不断放大的同时也要放绝大多的精力在某一个具体领域中探求，前提是你要清楚找准了自己想要专精的领域。不过这就是难处了，大多都是在迷茫中啊。

失败了不可怕，可怕的是失败后无法重拾的心。

每年要给自己定些目标。用一张图来结束此篇：

直接开搞。

toString

该方法进行了重载，一种是 toString(int i, int radix)，另一个是 toString(int i)。一个参数的方法就相当于 toString(int i, 10)，看代码便知，何况其官网注释也有：

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

public static String toString(int i, int radix) {
    if (radix < Character.MIN_RADIX || radix > Character.MAX_RADIX)
        radix = 10;

    /* Use the faster version */
    if (radix == 10) {
        return toString(i);
    }
    // int 32位
    char buf[] = new char[33];
    boolean negative = (i < 0);
    int charPos = 32;

    if (!negative) {
        i = -i;
    }
    // 根据进制取余转换
    while (i <= -radix) {
        buf[charPos--] = digits[-(i % radix)];
        i = i / radix;
    }
    buf[charPos] = digits[-i];

    if (negative) {
        buf[--charPos] = '-';
    }

    return new String(buf, charPos, (33 - charPos));
}

不过该方法需注意： If the first argument is negative, the first element of the result is the ASCII minus character '-' ('\u005Cu002D'). If the first argument is not negative, no sign character appears in the result. 例如：

1
2

Integer.toString(-44, 2)  // -101100
Integer.toBinaryString(-44) // 11111111111111111111111111010100

若是负数，用该方法求得的值只是正数前加了个 “-“ 。

toBinaryString

类似的几个方法也一并列出了。 toBinaryString(int i) 转二进制方法，toOctalString(int i) 转八进制方法，toHexString(int i) 转十六进制方法。

1
2
3

Integer.toBinaryString(-44) // 11111111111111111111111111010100
Integer.toOctalString(44) // 54
Integer.toHexString(44) // 2c

parseUnsignedInt

与 toString 方法一样进行了重载。 parseUnsignedInt(String s) 与 parseUnsignedInt(String s, int radix) 这是 JDK 1.8 新增的方法，作用就是将字符串参数解析为第二个参数指定的基数中的无符号整数。

1
2
3

Integer.parseUnsignedInt("11111111111111111111111111010100", 2) // -44
Integer.parseUnsignedInt("44", 10) // 44
Integer.parseUnsignedInt("44") // 44

decode

该方法将 String 解码为整数。 接受指定语法的十进制，十六进制和八进制数。源码如下：

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

public static Integer decode(String nm) throws NumberFormatException {
    int radix = 10;
    int index = 0;
    boolean negative = false;
    Integer result;

    if (nm.length() == 0)
        throw new NumberFormatException("Zero length string");
    char firstChar = nm.charAt(0);
    // Handle sign, if present
    if (firstChar == '-') {
        negative = true;
        index++;
    } else if (firstChar == '+')
        index++;

    // Handle radix specifier, if present
    if (nm.startsWith("0x", index) || nm.startsWith("0X", index)) {
        index += 2;
        radix = 16;
    }
    else if (nm.startsWith("#", index)) {
        index ++;
        radix = 16;
    }
    else if (nm.startsWith("0", index) && nm.length() > 1 + index) { // 0 后面长度要大于 1
        index ++;
        radix = 8;
    }

    if (nm.startsWith("-", index) || nm.startsWith("+", index))
        throw new NumberFormatException("Sign character in wrong position");

    try {
        result = Integer.valueOf(nm.substring(index), radix);
        result = negative ? Integer.valueOf(-result.intValue()) : result;
    } catch (NumberFormatException e) {
        // If number is Integer.MIN_VALUE, we'll end up here. The next line
        // handles this case, and causes any genuine format error to be
        // rethrown.
        String constant = negative ? ("-" + nm.substring(index))
                                   : nm.substring(index);
        result = Integer.valueOf(constant, radix);
    }
    return result;
}

使用测试如下：

1
2
3
4

Integer.decode("0xff") // 255
Integer.decode("#ff") // 255
Integer.decode("-07") // -7
Integer.decode("-071") // -57

highestOneBit

该方法返回一个 int 值，该值最多只有一位，位于指定 int 值中最高位（“最左侧”）1 的位置。 如果指定的值在其二进制补码表示中没有一位，即，如果它等于零，则返回零。

1

Integer.highestOneBit(44) // 32

44 对应的二进制为 0010 1100，只选中其最左侧的 “1” 那就是 0010 0000，也就是 2⁵ = 32

lowestOneBit

该方法返回一个 int 值，该值最多只有一位，位于指定 int 值中最低位（“最右侧”）1 的位置。 如果指定的值在其二进制补码表示中没有一位，即，如果它等于零，则返回零。

1

Integer.lowestOneBit(44) // 4

44 对应的二进制为 0010 1100，只选中其最右侧的 “1” 那就是 0000 0100，也就是 2² = 4

numberOfLeadingZeros

该方法计算首部零的个数。

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

/**
 * 首先在 jvm 中一个 int 类型的数据占 4 个字节，共 32 位，其实就相当于一个长度为 32 的数组。
 *
 * 那我们要计算首部 0 的个数，就是从左边第一个位开始累加 0 的个数，直到遇到一个非零值。
 */
public static int numberOfLeadingZeros(int i) {
    // HD, Figure 5-6
    if (i == 0)
        return 32;
    int n = 1;
    // 下面的代码就是定位从左边开始第一个非零值的位置，在定位过程中顺便累加从左边开始 0 的个数
    // 将 i 无符号右移 16 位后，有二种情况；
    //   情况1. i=0,则第一个非零值位于低 16 位，i 至少有 16 个 0，同时将 i 左移 16 位（把低 16 位移到原高 16 位的位置，这样情况 1 和情况 2 就能统一后续的判断方式）
    //   情况2. i!=0,则第一个非零值位于高 16 位，后续在高 16 位中继续判断
    // 这个思路就是二分查找，首先把32位的数分为高低 16 位，如果非零值位于高 16 位，后续再将高 16 位继续二分为高低 8 位，一直二分到集合中只有 1 个元素
    if (i >>> 16 == 0) { n += 16; i <<= 16; }
    // 判断第一个非零值是否位于高 8 位
    if (i >>> 24 == 0) { n +=  8; i <<=  8; }
    // 判断第一个非零值是否位于高 4 位
    if (i >>> 28 == 0) { n +=  4; i <<=  4; }
    // 判断第一个非零值是否位于高 2 位
    if (i >>> 30 == 0) { n +=  2; i <<=  2; }
    n -= i >>> 31;
    return n;
}

测试看看：

1

Integer.numberOfLeadingZeros(44) // 26

int 4 个字节，一个字节八位，所以有 32 位。44 对应完整二进制就是 0000 0000 0000 0000 0000 0000 0010 1100。所以从左边开始数起共有 26 个零。

numberOfTrailingZeros

返回指定 int 值的二进制补码表达式中最低位（“最右侧”）1 之后的零位数。

1

Integer.numberOfTrailingZeros(44) // 2

44 对应二进制 0010 1100。其最右侧 “1” 之后的零的个数就是 2。

bitCount

返回指定 int 值的二进制补码中 1 的个数。

1
2

Integer.bitCount(44) // 3
Integer.bitCount(-44) // 28

44 对应的二进制补码为 0000 0000 0000 0000 0000 0000 0010 1100。1 有 3 个。

-44 对应的二进制补码为 1111 1111 1111 1111 1111 1111 1101 0100。1 有 28 个。

前言

背包问题是比较经典的动态规划算法题，之前没接触过算法都没听说过这个，也是后来在 leetcode 中刷题时才了解到，惭愧惭愧啊。算法的世界太奇妙，数学一直都是那么令人着迷。今天来总结一下这个 01 背包问题。注：这里的物品不可拆分。

动态规划

首先了解下什么是动态规划。动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。1957年出版了他的名著《Dynamic Programming》，这是该领域的第一本著作。

动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。

详情可见：动态规划

问题详解

问题描述

给定 N 种物品和一个背包。物品i的重量是 Wi，其价值位 Vi，背包的容量为 C。问应该如何选择装入背包的物品，使得转入背包的物品的总价值为最大。

问题分析

在选择物品的时候，对每种物品只有两种选择，要么装入，要么不装入。因此，此为一个 0-1 背包问题。
01 背包的递归公式为：

1
2
3

m[i,0] = m[0,j] = 0
m[i,j] = m[i-1,j] ,j < wi
m[i,j] = max(m[i-1,j-wi]+vi, m[i-1,j]) ,j >= wi

其中，m[i,j]为前 i 件物品中选择若干件，放入承重为 j 的背包中，得到的最大的价值。

wi 为第 i 件商品的重量。

vi 为第 i 件商品的价值。

例题讲解

有编号为 a,b,c,d,e 的五件物品，他们的重量分别为 4,5,6,2,2，价值分别为 6,4,5,3,6，现在给你一个承重为 10 的背包，怎么实现价值最大。

根据上述公式可以得到一个数据表，表从上向下生成：

故可以根据公式码出如下实现代码：

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

public static void main(String[] args) {

    int n = 5;// 5件物品,物品编号为a,b,c,d,e（下面为多加一件物品，第一个物品为虚拟的物品）
    int weight[] = { 0, 4, 5, 6, 2, 2 };// 物品的重量
    int value[] = { 0, 6, 4, 5, 3, 6 }; // 对应物品的价值
    int c = 10; // 背包容量
    int state[] = { 0, 0, 0, 0, 0, 0 };// 开始状态
    char name[] = { ' ', 'a', 'b', 'c', 'd', 'e' };
    int maxValue = getMaxValue(n, weight, value, state, c);
    System.out.println("最大价值为 = " + maxValue);
    System.out.print("放入的物品为 ：");
    for (int i = 1; i <= 5; i++) {
        if (state[i] == 1) {
            System.out.print(name[i] + "  ");
        }
    }

    // System.out.println();
}

/**
 * 
 * @param n
 *            物品数量
 * @param weight
 *            物品对应重量（数组下标从0开始，故第一个物品为虚拟物品）
 * @param value
 *            物品对应价值（数组下标从0开始，故第一个物品为虚拟物品）
 * @param state
 *            物品的开始状态
 * @param c
 *            背包的容量
 * @return
 */
public static int getMaxValue(int n, int weight[], int value[], int state[], int c) {
    // n 为物品的数量，数组时需要加 1，此时可以从 0,1,...n 个物品，共 n+1 个商品，其中第 0 个为虚构物品
    // 对于物品的价值，可以写成 2 维数组
    int m[][] = new int[n + 1][c + 1]; // n 为 0,1,2...(n-1),背包重量为 0,1,2...C
    int i, j;

    for (i = 0; i <= n; i++) {
        m[i][0] = 0;
    }
    for (j = 0; j <= c; j++) {
        m[0][j] = 0;
    }

    for (i = 1; i <= n; i++) {
        // System.out.println();
        for (j = 1; j <= c; j++) {
            if (j < weight[i]) { // 新的物品太重，无法放下
                m[i][j] = m[i - 1][j];
            } else {// 分为放和不放 取较大值
                m[i][j] = Math.max(m[i - 1][j - weight[i]] + value[i], m[i - 1][j]);
            }
            // System.out.print("m["+i+"]["+j+"]="+m[i][j]+" ");
            // System.out.print(m[i][j]+" ");
        }
    }

    // 根据其最大价值，反向推断是否添加了物品 i

    j = c;
    for (i = n; i > 0; i--) {
        if (m[i][j] > m[i - 1][j]) {// 物品 i 添加到了序列列表
            state[i] = 1;
            j = j - weight[i];
        } else { // 没有添加
            state[i] = 0;
        }
    }

    return m[n][c]; // 最大价值
}

输出结果为：

1
2

最大价值为 = 15
放入的物品为 ：a  d  e  

具体实现看上述代码即可，注释齐全，简单易懂。

参考资料

• 动态规划之01背包问题（最易理解的讲解）
• 算法设计与分析–01背包问题（动态规划法解决）
• 01背包问题