2

我首先要说的是，即使我几个月前完成了软件工程师的工作，以下问题也不是出于家庭作业的目的。无论如何，今天我正在工作，一位朋友问我这个奇怪的排序问题。

“我有一个包含 1000 行的列表，每行代表一个数字，我想创建 10 个子列表，每个子列表都有类似的主列表中的数字总和。我该怎么做？”

例如，我有由 5,4,3,2 和 1 组成的主列表。这很简单，我创建了两个子列表，一个是 5 和 3，另一个是 4,2 和 1 每个列表的结果是相似的：8为前 7 为第二。

即使知道它很简单，我也无法弄清楚算法，但我错过了一些东西。

4

1 回答 1

3

设A为输入数组。我假设它是升序排序的。

A = [2,3,6,8,11]

让M[i]是到目前为止找到的子列表的数量等于i。

开始只是M[0] = 1因为有一个列表的总和为零，即空列表。

M = [1,0,0,...]

然后一个接一个地从列表中取出每个项目A。考虑到可以使用您刚拿的物品时，请更新您必须组成每个总和列表的方法的数量。

Suppose a is the new item
for each j:
    if M[j] != 0:
        M_next[j+a] = M[j+a] + M[j]

当您在此期间发现任何M[j]达到 10 时，您应该停止算法。另外，修改以记住列表中的项目，以便能够在最后获得实际列表！

笔记：

  • 您可以使用稀疏表示M
  • 这类似于那些背包和子集和问题。也许你会发现很多更好的算法阅读这些。

这是 Python 中的工作代码：

A = [2,3,6,8,11]
t = sum(A)
M = [0]*(t+1)
M[0] = 1

print 'init M :',M

for a in A:
    for j in range(len(M)-1,-1,-1):
        if M[j] != 0:
            M[j+a] += M[j]
    print 'use',a,':',M

及其输出：

init M : [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
use 2 : [1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
use 3 : [1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
use 6 : [1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
use 8 : [1, 0, 1, 1, 0, 1, 1, 0, 2, 1, 1, 2, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
use 11 : [1, 0, 1, 1, 0, 1, 1, 0, 2, 1, 1, 3, 0, 2, 2, 0, 2, 2, 0, 3, 1, 1, 2, 0, 1, 1, 0, 1, 1, 0, 1]

以M[11] = 3结尾的解释为例；这意味着有 3 个总和等于 11 的子列表。如果您跟踪进度，您可以看到子列表是{2,3,6},{3,8},{11}.

考虑到您允许 10 个子列表的总和相似的事实。不只是完全相同的金额。您可能希望将终止条件从“在任何 M[j] >= 10 时终止”更改为“在 sum(M[j:j+3]) >= 10 时终止”或类似的东西。

于 2013-06-06T14:55:45.257 回答