python - プログラム、10から最高のものを選択します

Question

配列から車を選択するPythonのプログラムを作成する必要があります。このプログラムは、10台の車の質量で満たされています。アイデアは、それが最も効果的に最大8トンを保持できるはしけを埋め、最小のスペースを埋めないままにするというものです。私の考えは、質量を変化させて、最大重量に最も近いものを選択するというものです。しかし、私はアルゴリズムに慣れていないので、それを行う方法の手がかりがありません

Answer 1

これは1Dビンパッキング問題です。これはNPの問題であり、最適な解決策はありません。ただし、欲張りアルゴリズムを使用してこれを解決する方法があります。おそらく、phpclasses.org（bin-packing）で私のビンパッキングソルバーを試してみたいと思うでしょう。

グラフが無向で無向であり、各ノードが接続されていて、各ノードが接続されている場合、（n ^ 2-n）/2ペアのノードと全体的なn^2-nの可能性/組み合わせがあります。

1,2,3,4,5,...,64
2,1,X,X,X,...,X
3,X,1,X,X,...,X
4,X,X,1,X,...,X
5,X,X,X,1,...,X
.,X,X,X,X,1,.,X
.,X,X,X,X,X,1,X
64,X,X,X,X,X,X,1 

これは10台の車でも同じではありませんか？（45ペアの車と90の組み合わせ/可能性）。何か忘れましたか？エラーはどこにありますか？

Answer 2

この演習は動的計画法で解決します。O（m * n）演算で最適な解を得ることができるはずです（nは車の数、mは総質量）。ただし、これは、質量がすべて整数の場合にのみ機能します。

一般に、バイナリ線形計画問題があります。それらは一般的に非常に難しい（NP完全）。

ただし、どちらの方法でも、初心者向けの資料とは見なされないアルゴリズムが使用されます。（あなたが提案したように）試行錯誤する方が良いかもしれませんし、単にすべての可能な組み合わせを試してみてください。

Answer 3

ここにあるような問題は、セールスマンが都市のリストを訪問するための最も効率的な方法を求める、古典的な巡回セールスマン問題に似ています。違いは、はしけを埋めるためにすべての車を必要としないかもしれないのに対し、セールスマンはすべての都市を訪問しなければならないということです。しかし、問題は似ています。問題を解決するための強引な方法は、1台の車から10台すべての車まで、考えられるすべての車の組み合わせを調査することです。各車をいくつでも持つことが有効であると想定します（つまり、2号車がフォードフォーカスの場合、 3つのフォードフォーカスを持つことができます）。車のリストが特定の車の正確なリストである場合、これは簡単に変更できますが、使用できるのはそれぞれ1台だけです。

今、これはすぐに多くの時間を消費し始めます。車の数が増えると、車の可能な組み合わせの数が幾何学的に増えます。つまり、予想よりも少ない数の場合、プログラムの実行に時間がかかり、残りの時間があります。ただし、10は管理しやすいはずです（700,000を少し超える組み合わせ、または各アイテムを1つしか持てない場合は1024）。

まず、各車の重量と、はしけが運ぶことができる最大重量を定義します。

weights = [1, 2, 1, 3, 1, 2, 2, 4, 1, 2, 2]
capacity = 8

ここで、考えられるそれぞれの組み合わせを見つける方法が必要です。Pythonのitertoolsモジュールには、指定された長さのすべての組み合わせを提供する関数がありますが、すべての長さが必要です。したがって、1から10までのループを1つ作成しitertools.combinations_with_replacement、各長さを呼び出します。次に、各組み合わせの総重量を知ることができます。それがすでに見つけたどの重量よりも高いが、それでも容量の範囲内である場合は、これまでに見つけた中で最高のものとして記憶します。

ここでの唯一の本当の秘訣は、ウェイトの組み合わせが必要ないことです。ウェイトのインデックスの組み合わせが必要です。最後に、ウェイトではなく、バージに乗せる車を知りたいからです。だからcombinations_with_replacements(range(10), ...)ではなくcombinations_with_replacements(weights, ...)。ループ内では、組み合わせて各車の重量を取得しweights[i]て合計する必要があります。

もともとここにコードがありましたが、宿題なので取り出しました。:-)（元々そのようにタグ付けされていませんでしたが、知っておくべきでした-時間の変更を非難します。）

各車を1台だけ許可したい場合は、itertools.combinationsの代わりにを使用しますcombinations_with_replacement。

車の重量は1〜2トンであると他の場所で言及しているので、ショートカットが可能です。これは、少なくとも4台（4 * 2 = 8）が必要であることがわかっているため、1〜3台の車のすべての組み合わせをスキップできることを意味します。ただし、教授がパラメータを変更した場合、これは一般化されません。