算法训练——动态规划之背包问题系列

摘要

背包问题是一类经典的动态规划问题，它非常灵活，需要仔细琢磨体会，本文先对背包问题的几种常见类型作一个总结，然后再看看LeetCode上几个相关题目。

一、0-1背包问题（小偷问题）

你只有一个容量有限的背包，总容量为c，有n个可待选择的物品，每个物品只有一件，它们都有各自的重量和价值，你需要从中选择合适的组合来使得你背包中的物品总价值最大。

现在要从中选择物品装入背包中，要求物品的重量不能超过背包的容量，并且最后放在背包中物品的总价值最大。为什么叫做0/1背包呢？为什么不叫1/2背包，2/3背包？仔细想想，这里每个物品只有一个，对于每个物品而言，只有两种选择，盘它或者不盘，盘它记为1，不盘记为0，我们不能将物品进行分割，比如只拿半个是不允许的。这就是这个问题被称为0/1背包问题的原因。所以究竟选还是不选，这是个问题。

1.1 解法归纳:

一、如果装不下当前物品，那么前n个物品的最佳组合和前n-1个物品的最佳组合是一样的。

二、如果装得下当前物品。

• 假设1:装当前物品，在给当前物品预留了相应空间的情况下，前n-1个物品的最佳组合加上当前物品的价值就是总价值。
• 假设2:不装当前物品，那么前n个物品的最佳组合和前n-1个物品的最佳组合是一样的。

选取假设1和假设2中较大的价值，为当前最佳组合的价值。

package 背包问题;

import org.junit.Test;

/**
 * @Classname Package0_1
 * @Description TODO
 * @Date 2022/3/24 22:21
 * @Created by xjl
 */
public class OnePackage {
    /**
     * @description 0-1背包问题的算法
     * @param: i
     * @param: c
     * @date: 2022/3/24 22:55
     * @return: int
     * @author: xjl
     */
    private int OnePackage(int[] v, int[] w, int k, int c) {
        int[][] result = new int[k+1][c + 1];
        // 正式的1行1列的时候
        for (int i = 1; i