More
More
文章目录
  1. Acm 算法专题 0x00 01背包问题
    1. 什么是动态规划?
    2. 问题引入
    3. 建立模型

Acm 算法专题 0x00 01背包问题

Acm 算法专题 0x00 01背包问题

什么是动态规划?

要学习动态规划首先得了解何谓动态规划,维基百科给出的定义是

动态规划(英语:Dynamic programming,简称DP)是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。


问题引入

看了动态规划的定义你可能还是没有搞懂这是个什么玩意,那不如来看一个动态规划有关的问题:01背包问题

有N件物品和一个容量为V的背包。第i件物品的体积是v[i],价值是w[i]。求解将哪些物品装入背包可使价值总和最大。

要解决这个问题首先想到的解决方式是直接枚举遍历,这当然不失为一种办法。但直接遍历的时间复杂度为O(n^2),当N的值很大时计算出答案会需要非常非常多的时间。我们能不能找出一个方法来简化问题呢?

仔细思考我们会发现,直接遍历所有可能的情况之所以这么费时,是因为我们重复遍历了相同的“子问题”。比如遍历v1,v2, v3与v1, v2, v4时 重复遍历了v1, v2 这显然是不合算的
tree.jpg

建立模型

我们不妨先建立一个有关此问题的模型
我们定义函数 F(i, v) 为存放 i 个物品且使用的空间为 v 时背包中物品的价值
w(i) 为第 i 件物品的价值 v(i) 为第 i 件物品的体积
则可以发现要使得 F(i, v) 最大,只需要在 F(i - 1, u) 最大的情况下再在背包里加一件物品 k 使得

F(i - 1, u) + w(k)

不超出限制且价值最大,即令

F(i, u + v(k)) = F(i - 1, u) + w(k)

那么显然有

u = v - v(k)

所以

F(i, v) = F(i - 1, v - v(k)) + w(k)

只有当 w(k) 最大时上式才成立,我们可以推出更一般的情况,对于 x, 若 F(i - 1, v - v(x)) + w(x) < F(i - 1, v) 时, 则令

F(i, v) = F(i - 1, v)

综上显然有

F(i, v) = max{ F(i - 1, v), F(i - 1, v - v(x)) + w(x) }

就此我们得出了01背包问题的 状态转移方程


下面给出解决问题的核心部分代码:

1
2
3
4
5
for(int i = 1; i <= N; i++) {
for (int j = 1; j <= V; j++) {
f[i][j] = max(f[j], f[j - v[i]] + w[i]);
}
}