查找曲目按長度

Question

那場比賽組

有人可以想出一個解決這個問題，在選擇的編程語言（最好是Python，但任何事情都可能被罰款我猜）：

我有不同的軌道長度組，讓我們說：

10:03 
24:23 
... 

和源跟蹤自己：

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

，我需要以務實的態度尋找追蹤屬於上述長度組。作爲例子在頭兩個軌跡屬於第1組爲它們的總和長度等於組長度

在此先感謝

編輯：這不是我的家庭作業，時間是長了（我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

看那itertools的Python模塊：

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

它支持以計算軌道的所有可能的排列（）和組合（）。

其餘的由你決定（不做你真正的家庭作業）。

Answer 2

這是一個硬通用NP-complete問題，號稱爲Knapsack problem。您可以查看維基百科文章，瞭解其解決方案的常見方法，但在一般情況下並不那麼容易或快速。您也可以在這裏檢查knapsack-problem標籤。