Documentation
¶
Index ¶
- func GroupKnapsack(groups [][]struct{ ... }, maxW int) int
- func GroupKnapsackFill(groups [][]int, maxW int) []bool
- func GroupKnapsackWaysToSum(stocks, weights []int, maxW int) int
- func LIS(nums []int) int
- func LISGreedy(nums []int) int
- func LISPath(nums []int) []int
- func MemorySearch[X comparable, Y any](dfs *func(X) Y) (_cache map[X]Y)
- func MemorySearch2[X, Y comparable, Z any](dfs *func(X, Y) Z) (_cache map[[2]any]Z)
- func MemorySearch3[X, Y, Z comparable, R any](dfs *func(X, Y, Z) R) (_cache map[[3]any]R)
- func UnboundedKnapsack(values, weights []int, maxW int) int
- func UnboundedKnapsackAtLeastFillUp(values, weights []int, maxW int) int
- func UnboundedKnapsackExactlyFull(values, weights []int, maxW int) int
- func UnboundedKnapsackWaysToSum(nums []int, sum int) int
- func ZeroOneKnapsack(values, weights []int, maxW int) int
- func ZeroOneKnapsackAtLeastFillUp(values, weights []int, maxW int) int
- func ZeroOneKnapsackExactlyFull(values, weights []int, maxW int) int
- func ZeroOneWaysToSum(nums []int, sum int) int
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func GroupKnapsack ¶
GroupKnapsack 分组背包·每组至多选一个 LC2218 https://leetcode.cn/problems/maximum-value-of-k-coins-from-piles/
func GroupKnapsackFill ¶
GroupKnapsackFill 分组背包·每组恰好选一个 允许物品重量为 0 https://atcoder.jp/contests/abc240/tasks/abc240_c LC1981 https://leetcode-cn.com/problems/minimize-the-difference-between-target-and-chosen-elements/ 与二分图染色结合 https://codeforces.com/problemset/problem/1354/E 转换 https://codeforces.com/problemset/problem/1637/D
func GroupKnapsackWaysToSum ¶
GroupKnapsackWaysToSum 方案数
https://www.luogu.com.cn/problem/P1077 （可以用前缀和优化） LC2585 https://leetcode.cn/problems/number-of-ways-to-earn-points/
func LIS ¶
LIS 返回最长递增子序列的长度
LC300 https://leetcode.cn/problems/longest-increasing-subsequence/ LC1626 https://leetcode.cn/problems/best-team-with-no-conflicts/ - 时间复杂度：O(n^2)。 - 空间复杂度：O(n)。
func LISGreedy ¶
LISGreedy
贪心下二分
LC1964 https://leetcode.cn/problems/find-the-longest-valid-obstacle-course-at-each-position/ 需转换： - LC354 https://leetcode.cn/problems/russian-doll-envelopes
- 时间复杂度：O(nlogn) - 空间复杂度：O(n)。
func LISPath ¶
LISPath 返回最长递增子序列本身，需要额外的 Last 字段来记录是从哪里转移过来的
LC2901 https://leetcode.cn/problems/longest-unequal-adjacent-groups-subsequence-ii/
- 时间复杂度：O(n^2)。 - 空间复杂度：O(n)。
func MemorySearch ¶
func MemorySearch[X comparable, Y any](dfs *func(X) Y) (_cache map[X]Y)
MemorySearch 实现 Python 的 cache 装饰器，返回 cache 用于 debug
func MemorySearch2 ¶
func MemorySearch2[X, Y comparable, Z any](dfs *func(X, Y) Z) (_cache map[[2]any]Z)
MemorySearch2 todo 整合 MemorySearch
实现 Python 的 cache 装饰器，返回 cache 用于 debug
func MemorySearch3 ¶
func MemorySearch3[X, Y, Z comparable, R any](dfs *func(X, Y, Z) R) (_cache map[[3]any]R)
MemorySearch3 todo 整合 MemorySearch
实现 Python 的 cache 装饰器，返回 cache 用于 debug
func UnboundedKnapsack ¶
UnboundedKnapsack 完全背包 更快的做法 https://www.zhihu.com/question/26547156/answer/1181239468 https://github.com/hqztrue/shared_materials/blob/master/codeforces/101064%20L.%20The%20Knapsack%20problem%20156ms_short.cpp https://www.luogu.com.cn/problem/P1616 至少 https://www.luogu.com.cn/problem/P2918 恰好装满 LC322 https://leetcode.cn/problems/coin-change/ EXTRA: 恰好装满+打印方案 LC1449 https://leetcode.cn/problems/form-largest-integer-with-digits-that-add-up-to-target/ 【脑洞】求极限：lim_{maxW->∞} dp[maxW]/maxW
func UnboundedKnapsackAtLeastFillUp ¶
UnboundedKnapsackAtLeastFillUp 至少装入重量和为 maxW 的物品，求价值和的最小值 https://www.luogu.com.cn/problem/P2918
func UnboundedKnapsackExactlyFull ¶
UnboundedKnapsackExactlyFull 完全背包变形：恰好装满时的 最大价值和 / 最小价值和 /方案数 最小价值和：LC322 https://leetcode.cn/problems/coin-change/ 方案数： LC518 https://leetcode.cn/problems/coin-change-ii/
func UnboundedKnapsackWaysToSum ¶
UnboundedKnapsackWaysToSum 完全背包，恰好装满背包时的方案数 LC518 https://leetcode.cn/problems/coin-change-ii/
func ZeroOneKnapsack ¶
ZeroOneKnapsack 0-1 背包 (n 个物品，背包容量为 maxW，每个物品只能选 1 次) 状态：从前 i 个物品中选择若干个，当容量限制为 j 时能获得的最大价值和 i∈[0,n-1], j∈[0,maxW] 初始值：f(0,j)=0 j∈[0,maxW] 除开初始状态，每个状态有两个来源，决策为 max： - 不选第 i 个物品：f(i-1,j) -> f(i,j) - 选第 i 个物品：f(i-1,j-wi)+vi -> f(i,j) j ≥ wi
最优解为 f(n-1,maxW)
func ZeroOneKnapsackAtLeastFillUp ¶
ZeroOneKnapsackAtLeastFillUp 0-1 背包 EXTRA: 至少装入重量和为 maxW 的物品，求价值和的最小值 https://www.luogu.com.cn/problem/P4377 f[0] 表示至少为 0 的情况，也表示没有任何约束的情况 比如选第 i 个物品后容量 <=0 了，那就表示前面的 i-1 个物品可以不受约束地随意选或不选了 - 转换 https://codeforces.com/problemset/problem/19/B LC2742 https://leetcode.cn/problems/painting-the-walls/ 二维费用的情况+价值最小 https://ac.nowcoder.com/acm/contest/6218/C
func ZeroOneKnapsackExactlyFull ¶
ZeroOneKnapsackExactlyFull 01背包变形：恰好装满 https://leetcode.cn/contest/sf-tech/problems/cINqyA/ LC 2915 https://leetcode.cn/problems/length-of-the-longest-subsequence-that-sums-to-target/ LC 416 https://leetcode.cn/problems/partition-equal-subset-sum/
func ZeroOneWaysToSum ¶
ZeroOneWaysToSum 0-1 背包 EXTRA: 从序列 a 中选若干个数，使其总和为 sum 的方案数 常见题目是算严格分拆（必须用不同数字） LC2787 https://leetcode.cn/problems/ways-to-express-an-integer-as-sum-of-powers/ - https://oeis.org/A000009 NOTE: 1,1,1,...1(32个1),s-32,s-31,...,s 可以让方案数恰好为 2^32 二维+上限+下限 LC879 https://leetcode.cn/problems/profitable-schemes/ https://atcoder.jp/contests/arc060/tasks/arc060_a https://codeforces.com/problemset/problem/1673/C
- 转换 https://atcoder.jp/contests/abc169/tasks/abc169_f https://codeforces.com/problemset/problem/478/D LC494 https://leetcode.cn/problems/target-sum/ LC1434 https://leetcode.cn/problems/number-of-ways-to-wear-different-hats-to-each-other/ 由于顺序不同也算方案，所以这题需要正序递推 LC377 https://leetcode.cn/problems/combination-sum-iv/
Types ¶
This section is empty.
Source Files