算法-动态规划-0-1背包问题（二维0-1背包，背包求方案数，求背包具体方案）

概念

背包问题（Knapsack Problem）是算法领域的经典组合优化问题，在资源分配等场景有广泛应用，以下从定义、常见类型、解决方法等方面介绍：

定义

给定一组物品，每个物品都有自己的重量和价值，在限定背包容量的情况下，如何选择物品放入背包，使得装入背包的物品总价值最大，同时不超过背包的容量限制。

常见类型

|0 - 1 背包问题：每个物品只有取或不取两种状态（1 表示取，0 表示不取），不能取部分物品。例如，有多个不同重量和价值的宝石，背包容量有限，决定选取哪些宝石能获得最大价值。

|完全背包问题：每个物品可以无限次选取。比如商店里有不同价格和体积的商品，购物袋容量固定，考虑每种商品购买多少件能使总价值最高。

|多重背包问题：每个物品有一定的数量限制，只能在数量范围内选取。像仓库里有不同类型且数量有限的货物，卡车运载量有限，决定装载哪些货物能实现最大收益。

0-1背包

问题描述

有(N)件物品和一个容量为(V)的背包。每件物品有两个属性，第(i)件物品的费用（占用背包的容量）是(c(i))，价值是(w(i))。需要求解将哪些物品装入背包，可使这些物品的费用总和不超过背包容量，且价值总和最大。

问题特点

每种物品只有一件，可以选择放或者不放，不存在取部分物品的情况，这也是 “0 - 1” 的含义，0 代表不放，1 代表放。

算法基本思想

通常利用动态规划思想求解。

定义子问题：(f(i)(v))表示前(i)件物品放入一个容量最多为(v)的背包可以获得的最大价值。 其状态转移方程为：(f(i)(v)=max{f(i - 1)(v),f(i - 1)(v - c(i)) + w(i)}) 。该方程的含义是，“将前(i)件物品放入容量为(v)的背包中” 这一问题，若只考虑第(i)件物品放或者不放，可转化为只涉及前(i - 1)件物品的问题：

|不放第(i)件物品：问题转化为 “前(i - 1)件物品放入容量为(v)的背包中”，此时最大价值为(f(i - 1)(v)) 。

|放第(i)件物品：问题转化为 “前(i - 1)件物品放入剩下的容量为(v - c(i)\)的背包中”，此时能获得的最大价值是(f(i - 1)(v - c(i)))再加上放入第(i)件物品获得的价值(w(i)) 。 (f(i)(v))的值取上述两种情况中的最大值。按照这个方程递推完毕后，最终的答案是(f(N)(V))，如果我们定义的子问题是前(i)件物品放入一个容量恰好为(v)的背包可以获得的最大价值，那么答案是(f(N)(0..V))中的最大值（因为(f(i)(v))有意义当且仅当存在一个前(i)件物品的子集，其费用总和为(v) ）。

引例：

分析：

这是一道以故事为背景的算法问题。主人公辰辰梦想成为伟大医师，为拜师，医师带他到满是草药的山洞，给出采药时间限制。每株草药有各自的采摘耗时和价值，要求辰辰在给定时间内采摘草药，使总价值达到最大。本质上是一个 0 - 1 背包问题，采药时间相当于背包容量，草药的采摘耗时和价值分别对应物品的重量和价值，需在时间限制内选择合适的草药（物品），以获取最大总价值。

 这是最简单的背包模型的变种，解题模版如下；

由于第i行的状态只和第i-1行有关，所以可以用滚动数组进行优化：

 习题1：

分析：

给定一个容量为\(V\)的箱子以及\(n\)个具有各自体积（正整数）的物品。目标是从这\(n\)个物品中选取若干个装入箱子，使得箱子剩余的空间最小。这等价于在箱子容量限制下，尽可能多地装入物品体积，即最大化已装入物品的总体积，类似于 0 - 1 背包问题中在背包容量限制下最大化物品总价值，只不过这里的 “价值” 体现为物品体积。通过合理选择物品的组合来实现对箱子空间的最优利用，需要运用算法策略如动态规划等求解。

这是一个背包问题的变种，要求我们去求出最小的剩余的空间，本质不就是求出能够得到的最大的体积吗？所以这里的价值就是体积。我们的f[i][j]还是表示的前i个物品，体积不超过j所能获得的最大的价值，答案就是v-f[n][v]，利用滚动数组来优化一下空间，答案就是v-f[v]

伪代码如下：

习题2（二维0-1背包）：

分析：

这是一个二维0-1背包问题，我们纪要去关注皮卡丘的体力，也要去关注精灵球的数量，所以有两个花费，我们的关注的子问题就是f[i][j][k]，即只抓前i个小精灵，花费不超过j个精灵球，体力消费不超过k所能抓住的最多的小精灵数量。

因为还要求花费最少的体力，所以我们要找到最小的k使得f[N][M][k]==f[N][M][K]

使用滚动数组可以优化第一维

伪代码：

习题3（求方案数）：

分析

我们的子问题f[i][j]表示的是前i个数，组成数j的方案数

这是一个求方案数的0-1问题，特殊的点是初始化的时候，我们对f[0][0]的初始化为1，f[0][j],(j!=0)为0.

状态转移方程是f[i][j]=f[i-1][j]+f[i-1][j-c[i]]（不选第i个数组成j的方案数 + 选择第i个数组成j的方案数）

伪代码如下

习题4：（求具体方案）

分析：

这是一道典型的 0 - 1 背包问题拓展题目。给定 (N) 件物品和一个容量为 (V) 的背包，每件物品仅能使用一次，第 (i) 件物品具有体积(v_i) 和价值 (w_i) 两个属性。

需找出将哪些物品装入背包，能使物品总体积不超背包容量 \(V\) 的同时，总价值达到最大。并且，在满足总价值最大的众多方案中，要输出所选物品编号构成序列的字典序最小的方案。

相比普通 0 - 1 背包问题仅需计算最大价值，本题额外增加了输出字典序最小方案的要求，这使得解题过程不仅要考虑价值最优，还需在回溯确定选取物品时，按照字典序规则来选择方案。

我们要根据我们自己的转移方程来确定转移的方向：

伪代码：