和最接近某个数的子集

2022/7/7 6:21:26

本文主要是介绍和最接近某个数的子集,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

对于整数集合 \(S\),最大元素为 \(m\),则可以在 \(m|S|\) 时间内求出和最接近某整数 \(C\) 的子集,在元素不大时比暴力背包优。做法如下:

将 \(S\) 看作一个序列并选择一个最长前缀 \(b\),满足和小于 \(C\)。

为了减小值域,考虑一种简单的方法可以使中间结果始终在 \([C - m, C + m]\) 内,并导出一个 DP。

设最优答案为 \(X\),当前答案为 \(A\)。

现在加入元素 \(i\),若 \(i \not \in X\),则不操作,否则尝试将 \(i\) 加入 \(A\),并保持和在 \([C - m, C + m]\) 内。如果可以加入就直接加入,否则不断删除标号最大的不在 \(X\) 中的元素 \(j\),直到可以加入。不难发现这样一定可以将 \(A\) 最终变成 \(X\),并且只需要维护 \(A\) 的最长全选前缀,而非整个集合 \(A\)。

设 \(f(i ,s)\) 表示前 \(i\) 个元素,表示出和 \(s\),最长全选前缀是多少。初始为 \(f(b, \sum_{i \le b}S_i) \gets b\)。

先做加入 \(i\) 的转移,再做枚举 \(f(i, s)\) 前缀中一个数删除的转移。注意如果枚举删除 \(k \le f(i - 1, s)\),那么 \(k\) 可以在 \(i - 1\) 时刻删除,这次就不用枚举了。所以对于每个 \(s\),\(k\) 的枚举总和是 \(O(|S|)\) 的,所以总复杂度 \(\mathcal O(m|S|)\)。



这篇关于和最接近某个数的子集的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程