1

有人可以用选择的编程语言(最好是Python,但我猜任何事情都可以)想出一个解决这个问题的方法:

我有各种轨道长度组,比方说:

10:03
24:23
...

和源轨道本身:

1:03
9:00
4:24
...

我需要务实地找到哪些曲目属于上述长度组。例如,前两个轨道属于第一组,因为它们的总长度等于组长度

提前致谢

编辑:这不是我的作业,因为那个时间已经过去了(我已经 30 多岁了),但这是我遇到的问题,而且我不是程序员。我会看看itertools,谢谢

编辑2:感谢您的建议。我制作了 Python 脚本,如果对我来说运行良好且快速。它肯定没有优化,但这里是骨架:

from itertools import combinations

tracks = [1,2,3,4,5,6,7,8,9]
group = 7

d_key, valid_tracks, possible_group =0, [], {}

for i in sorted(tracks):
    if i < group: valid_tracks.append(i)

for j in range(len(valid_tracks) - 2):
    for k in combinations(valid_tracks, len(valid_tracks) - 1 - j):
        if sum(k) <= group:
            if sum(k) == group:
                d_key += 1
                possible_group[d_key] = k

print possible_group

我很高兴我解决了这个问题,因为手动跟踪这将花费我更多的时间,哈哈

4

2 回答 2

0

查看 Python 的 itertools 模块:

http://docs.python.org/library/itertools.html

它支持计算轨道的所有可能的排列()和组合()。

其余的取决于你(不做你真正的功课)。

于 2011-04-16T06:41:52.340 回答
0

这是一个困难的一般NP 完全问题,称为背包问题。您可以查看维基百科文章以了解其解决方案的常用方法,但在一般情况下它不会那么容易或快速。您也可以在此处查看背包问题标签。

于 2011-04-16T07:01:57.080 回答