1

誰かがこの問題の解決策を、選択したプログラミング言語 (できれば Python ですが、何でもいいと思います) で考え出すことができますか?

さまざまなトラック長グループがあります。たとえば、次のようにします。

10:03
24:23
...

およびソース トラック自体:

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

そして、上記の長さのグループに属するトラックを実用的に見つける必要があります。例のように、最初の 2 つのトラックは、合計の長さがグループの長さに等しいため、最初のグループに属します。

前もって感謝します

編集：それは私の宿題ではありませんが、それは私が抱えている問題であり、私はプログラマーではありません。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

これを手動で追跡すると、私の人生よりも時間がかかるので、これを解決してよかったです。

4

2 に答える 2

0

これは、ナップザック問題として知られている難しい一般的なNP 完全問題です。そのソリューションへの一般的なアプローチについては、ウィキペディアの記事を確認できますが、一般的にはそれほど簡単でも高速でもありません。ここでknapsack-problemタグを確認することもできます。

于 2011-04-16T07:01:57.080 に答える
0

Python の itertools モジュールを見てください。

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

トラックのすべての可能な permutations() とcombination() の計算をサポートしています。

残りはあなた次第です（本当の宿題はしません）。

于 2011-04-16T06:41:52.340 に答える