总览

这个月 Leetcode 彷佛开启了背包专场，连着数天都是经典的背包问题。于是我在这里决定就背包问题进行整理，记录个人心得。这里整理的是最为常见的0-1背包、完全背包和多重背包。

0-1 背包问题

1. 问题描述

这是最经典的背包问题，题目的风格概括而言可以是：一堆有限的物品（物品不一定非得是一个，只要有限都可以简化为0-1背包问题），每个物品有其对应的价值，然后有一个容积一定的容器，问怎么装才能获得最大价值。

2. 问题分析

先从为什么这个题可以用动态规划解决说起：动态规划指一个较复杂的求优问题可以拆解为若干个相互联系的阶段，每个阶段的决策需要考虑当前所处状态，且该阶段的决策会影响之后的决策。

背包问题中，需要考虑的状态主要是当前可选物品和当前可用空间，据此我们推导出状态矩阵应当是$dp[i][V]$，它表示在可选物品为$[0, i-1]$、可用空间为$volume$时可以获取的最大价值。进一步的，我们定义状态转移矩阵 :

$$dp[i][V]=max(dp[i-1][V-w[i]]+v[i], dp[i-1][V])$$

上式中，$i$代表物品的编号，$V$代表容器当前的体积，$v$代表物品的价值，$w$数组中记录着物品所占体积。该状态转移矩阵比较了新物品引入时，装入它和不装入它所获得的价值大小，从而推导出当前阶段的最优解。观察该状态转移矩阵不难发现，当前阶段的结果只与$i-1$阶段有关，所以只要保证逆序推导，即使省略掉**$i$维度**的数据也是可行。

最终，核心循环如下:

1
2
3
4
5

// n 代表商品数目
for(int i = 0; i < n; ++i){
    for(int j = V; j >= w[i]; --j)
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
}

例题：Leetcode-416，Leetcode-1049

上述两题与传统背包问题的区别在于：传统问题要求选择的物品不能超过给定的容积，而Leetcode-416必须恰好等于总容积的一半，Leetcode-1049是必须尽可能接近一半。至于价值，物品的价值就是物品自身的值。

完全背包问题

1. 问题描述

概括描述：有多类商品且数目不限，第$i$类物品的价值为$v[i]$，重量为$w[i]$，怎样把它们装进一个容积一定的容器才能获得最大的价值。

2. 问题分析

完全背包和0-1背包最大的区别就是物品的数目不限，但依阶段逐步推优的思路是不变的，只是引入当前商品后，我们可以继续考虑当前商品是否可以装入容器。所以我们仍然可以写出状态转移矩阵:

$$dp[i][V]=max(dp[i][V-w[i]]+v[i], dp[i-1][V])$$

与0-1背包问题一样，这个二维矩阵也可以转换为一维矩阵。观察上式不难发现：若要装入当前商品，那么结果只与考虑了当前商品的结果有关；不装入商品，则结果只与未考虑当前商品的结果有关。因此只要保证顺序推导，我们就能将其简化为一维数组。

最终，核心循环如下:

1
2
3
4
5
6
7

// n 代表商品数目
for(int i = 0; i < n; ++i){
    for(int j = 0; j <= V; ++j){
        if(j >= w[i])
        	dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    }
}

例题：Leetcode-377，Leetcode-硬币，Leetcode-1449

除了求最大价值，一种十分常见的问题是求组合数，上述的前两题均是如此

多重背包问题

1. 问题描述

概括描述：有多类物品，第$i$类物品的价值为$v[i]$，重量为$w[i]$，数目为$n[i]$，问如何把它们装进一个容积一定的容器中，才能使获得的价值最大。

2. 问题分析

一个很朴素但又很有效的方法是把这类问题作为 0-1 问题的拓展，将其的种类总数看作 $种类数目*每类数目$，之后用 0 - 1背包的解法即可。

延伸问题：多维背包

之前讨论中，背包只有一个限制即背包的重量，如果引入新的限制，那么一维背包问题也就延伸为多维背包问题。对于这种问题，一个基本的思想是：有多少限制，加多少维度。然后再用一维背包问题的思想去解决

例题: Leetcode-879

本题中属于二维的0-1背包问题，在确定了员工数和收益这两个维度的限制后，套用0-1背包的思想，保证逆序推导即可得出答案