论文标题
部分可观测时空混沌系统的无模型预测
On Problems Related to Unbounded SubsetSum: A Unified Combinatorial Approach
论文作者
论文摘要
无界的子集是一个经典的教科书问题：给定整数$ W_1，W_2，\ CDOTS，W_n \在[1，U]，U]，〜C，U $中，我们需要查找是否存在$ M_1，M_1，M_2，\ CDOTS，CDOTS，M_N \ m_n \ in \ MATHBB {N} $ c = $ c = $ c = $ c = \ sum_}在其全目标版本中，给出了$ t \ in \ mathbb {z} _+$，并为所有整数$ c \ in [0，t] $回答。在本文中，我们研究了这个简单问题的三个概括：所有目标无绑背，所有目标共同汇和残留桌。通过对解决方案结构的新组合见解，我们为这些问题提供了一种新颖的两相方法。结果，我们介绍了第一个用于共汇和残基表的接近线性算法，该算法以$ \ tilde {o}（u+t）$和$ \ tilde {o}（u}（u）$确定性确定性地运行。我们还证明了是否可以计算$ n $ l-length阵列在$ t（n）$时间中的$（\ min，+）$卷积，然后可以将所有目标无绑的背包求解，以$ \ tilde {o}（t（u）+t）$时间来求解，从而建立了$ quadratic equivalence，从而建立了$ quivalentic equivalence nob-quadratic novivalence unbonget ublowed knapsack and $（+）$（+）$（+），+（+），+f。
Unbounded SubsetSum is a classical textbook problem: given integers $w_1,w_2,\cdots,w_n\in [1,u],~c,u$, we need to find if there exists $m_1,m_2,\cdots,m_n\in \mathbb{N}$ satisfying $c=\sum_{i=1}^n w_im_i$. In its all-target version, $t\in \mathbb{Z}_+$ is given and answer for all integers $c\in[0,t]$ is required. In this paper, we study three generalizations of this simple problem: All-Target Unbounded Knapsack, All-Target CoinChange and Residue Table. By new combinatorial insights into the structures of solutions, we present a novel two-phase approach for such problems. As a result, we present the first near-linear algorithms for CoinChange and Residue Table, which runs in $\tilde{O}(u+t)$ and $\tilde{O}(u)$ time deterministically. We also show if we can compute $(\min,+)$ convolution for $n$-length arrays in $T(n)$ time, then All-Target Unbounded Knapsack can be solved in $\tilde{O}(T(u)+t)$ time, thus establishing sub-quadratic equivalence between All-Target Unbounded Knapsack and $(\min,+)$ convolution.
