17117

DP

STL(12) WEB(13) 图论(6) 基本数据结构(5) 基础算法(5) 搜索(3) 进阶数据结构(4) 题解(7)

/ 注册

全部文章 / DP （共6篇）

多重背包来自专栏

问题有 n 种物品，其中第 i 种物品的体积为v[i]，价值为w[i]，并且有c[i]个，有一个容积为 m 的背包，选若干个物品装入背包，求解将哪些物品装入背包可使这些物品的总体积不超过背包容量，且价值总和最大。时间复杂度 ...

2020-10-12

0 440

分组背包来自专栏

问题有 n 组物品，其中第 i 组有 c[i] 个物品。第 i 组的第 j 个物品体积为 v[i][j] 价值为w[i][j]。有一组容积为 m 的背包，每组最多选一个物品装入背包，求解将哪些物品装入背包可使这些物品的总体积不超过背包容量，且价值...

2020-10-12

0 675

完全背包来自专栏

问题有 n 件物品和一个容量为 m 的背包。第 i 件物品的体积是 v[i]，价值是 w[i]。并且有无数多个求解将哪些物品装入背包可使这些物品的总体积不超过背包容量，且价值总和最大。时间复杂度 O( nm ) 状态表示 ...

2020-10-12

0 483

01背包来自专栏

问题有 n 件物品和一个容量为 m 的背包。第 i 件物品的体积是 v[i]，价值是 w[i]。求解将哪些物品装入背包可使这些物品的总体积不超过背包容量，且价值总和最大。时间复杂度 O( nm ) 状态表示 f...

2020-10-12

0 569

子序列来自专栏

Dilworth 定理最长不上升子序列的最少划分数 == 最长上升子序列长度（LIS） LIS 状态表示 dp[i] 表示以a[i] 为结尾的最长上升子序列长度状态转移方程 dp[i] = max{ dp[j] + 1 }; ...

2020-10-10

0 602

dp 来自专栏

作者：徐凯强 Andy链接：https://www.zhihu.com/question/23995189/answer/35324479来源：知乎著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。动态规划的本质不在于是递推或是递归，也不需要纠结是不是内存换时间。理解动态规划并...

2020-10-08

0 2310