查找按长度分组匹配的曲目

Question

有人可以用所选的编程语言（最好是Python，但我猜任何东西都可以）提出这个问题的解决方案：

我有各种轨道长度组，比方说：

10:03
24:23
...

和源轨道本身：

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

我需要找到实际上哪些曲目属于上述长度组。如示例所示，前两首曲目属于第一组，因为它们的总长度等于组长度

提前感谢

编辑：这不是我的作业，因为那段时间已经过去了（我已经超过 30 岁了），但这是我遇到的问题，我我不是程序员。我会看看 itertools，谢谢

edit2：谢谢你的建议。我制作了 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

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

Answer 1

查看Python的itertools模块：

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

它支持计算曲目所有可能的排列（）和组合（）。

剩下的就取决于你了（不做你真正的作业）。

Answer 2

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