Найти треки, соответствующие группе по длине - PullRequest
1 голос
/ 16 апреля 2011

Может кто-нибудь, пожалуйста, придумать решение этой проблемы, на выбранном языке программирования (желательно Python, но я думаю, все может быть хорошо):

У меня есть различные группы длины дорожки, скажем:

10:03
24:23
...

и сами треки источника:

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

, и мне нужно прагматично найти, какие треки принадлежат к группе выше длины.Как в примере, первые два трека принадлежат первой группе, так как их общая длина равна длине группы

Заранее спасибо

edit: Это не моя домашняя работа, так как это время давно прошло (яза 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

Я рад, что решил это, так как отслеживание этого вручную отнимет у меня больше времени, ха-ха

Ответы [ 2 ]

0 голосов
/ 16 апреля 2011

Это сложная общая NP-полная проблема, известная как Проблема с рюкзаком .Вы можете проверить в статье в Википедии общие подходы к ее решению, но в общем случае это будет не так просто и быстро.Вы также можете проверить тег рюкзак здесь.

0 голосов
/ 16 апреля 2011

Посмотрите на модуль itertools в Python:

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

Поддерживает вычисление всех возможных перестановок () и комбинаций () треков.

Остальное зависит от вас (не выполняя настоящую домашнюю работу).

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...