论文标题
在背包约束下的最大分区和额外分区
Sum-of-Max Partition under a Knapsack Constraint
论文作者
论文摘要
序列分区问题在许多领域都出现，例如顺序数据分析，信息传输和并行计算。在本文中，我们研究以下分区问题变体：给定$ n $ $ 1，\ ldots，n $的顺序，其中每个项目$ i $与权重$ w_i $和另一个参数$ s_i $相关，将顺序分配为几个连续的子序列，每个子序列的总重量不超过threshold $ w_0 $ w_0 $ w_0 $ w_0 $ w_0 $ w_0 $ sar，最小化。 这个问题承认基于动态编程的简单解决方案，该解决方案的价格为$ O（n^2）$时间，可以将其提高到$ O（n \ log n）$时间。我们的贡献是$ o（n）$ time算法，这是不平淡但易于实施的。我们还研究了相应的树分区问题。我们证明了树上的问题是NP完整的，我们提出了一个$ O（W_0 N^2）$ time（$ O（w_0^2n^2）$时间，分别为单位重量（分别为整数）情况。
Sequence partition problems arise in many fields, such as sequential data analysis, information transmission, and parallel computing. In this paper, we study the following partition problem variant: given a sequence of $n$ items $1,\ldots,n$, where each item $i$ is associated with weight $w_i$ and another parameter $s_i$, partition the sequence into several consecutive subsequences, so that the total weight of each subsequence is no more than a threshold $w_0$, and the sum of the largest $s_i$ in each subsequence is minimized. This problem admits a straightforward solution based on dynamic programming, which costs $O(n^2)$ time and can be improved to $O(n\log n)$ time easily. Our contribution is an $O(n)$ time algorithm, which is nontrivial yet easy to implement. We also study the corresponding tree partition problem. We prove that the problem on the tree is NP-complete and we present an $O(w_0 n^2)$ time ($O(w_0^2n^2)$ time, respectively) algorithm for the unit weight (integer weight, respectively) case.
