动态规划——背包问题

动态规划

动态规划的优化涉及到一般就是对动态规划的代码或方程做一个等价变形

0,1背包问题

描述

N个物品和容量为V的背包，每一个物品有两个属性 {重量\(w_i\),价值\(v_i\)}, 每件物品最多仅能用一次。

在背包能装得下的情况下，能选出的物品最大总价值为多少。

思路

先把基本的形式写出来，再一点点优化。背包问题的最优形式是用一维数组来表示，但是我们考虑一定要从最朴素的情况来考虑，然后再考虑优化。

从集合的角度来理解DP问题，DP中的每一个状态都表示一个集合，需要考虑清楚，f[i][j]表示的是哪一个集合，如背包问题就是所有选法的集合。

但实际上f[i][j]存储的是一个数，这个数就是集合的某种属性。集合表示什么呢？

集合表示的就是选法，即究竟选择了哪种选法，是选了第1，2，3个物品还是第4，5个物品，这个集合需要满足两个条件：

1. 只从前i个物品中选
2. 选出来的物品的总体积 \(\le\) j

满足这两个条件的所有选法的集合就是f[i][j]表示的集合，f[i][j]存储的是所有选法的价值的最大值。

具体如下图所示：

状态计算就是考虑f[i][j]可以被怎样计算出来，把所有的f[i][j]计算出来后，最终结果应为f[N][v]。

表示所有从前N个物品中选择出总体积 \(\le\) v的集合的总价值的最大值。

通过不停的将当前集合划分成若干个更小的集合，使每一个集合都可以用前面更小的集合表示出来。

如图中，将f[i][j]划分为包含i和不包含i这两个集合。

集合划分的原则：

1. 不重复，一个元素不要出现在两个集合，有些时候可以不满足
2. 不漏，必须满足。

完全背包问题

N个物品和容量为V的背包，每一个物品有两个属性 {重量\(w_i\),价值\(v_i\)}, 每件物品有无限个。

多重背包问题

N个物品和容量为V的背包，每一个物品有两个属性 {重量\(w_i\),价值\(v_i\)}, 每件物品最多有\(s_i\)个。

分组背包问题