Python。貪欲アルゴリズム、2つのループのリストを繰り返します。

Question

私はボックスに収まるアイテムの数に制約があり、移動する前にできるだけ多くのアイテムをボックスに収めなければならない欲張りアルゴリズムを作成しようとしています（すなわち、各箱の重量を最大化する）。

私はこれを2つの同一のリストを作成することで解決しようとしています。a_listとb_listとしましょう。

ここでは、各ボックスの制約は10です。たとえば、次のボックスに移動する前に、最初のアイテム（9）のみを1つに収めることができます。以下のボックスには、8 + 2

各ボックスには、現在の1がそれに嵌め込まさらにアイテムを持つことはできません一度私は、次のボックスに進むことができ

list_ = [[9], [8,2],[6,4].....] 

すなわちメインリスト内のリストで含まれている必要があります。

私は2つのリストを反復しようとしていますが、アイテムを削除する方法がわからないので、複数回表示されないようにlist_にしてください。

私は近づいていますが、私は2つのアイテムが2回出てきますが、1つはまったく出てこないのです。

私のリストを降順でソートしても、すべてのボックスが最適ではない場合もありますが、そのうちの1つに値 '2'のアイテムが1つしかありません。私はそれがループと関係があると知っていますが、なぜそれが降順で項目を通過していないのか分かりません。

limit = 10 
list_ = [[]] 

for i in a_list: 
    for j in b_list:    

     if sum(l[-1]) + i + j <= limit: 

      l[-1].append(i) 
      l[-1].append(j) 
      b_list.remove(j) 

     elif sum(l[-1]) + j <= limit: 
      l[-1].append(j) 
      b_list.remove(j) 

     else: 
      l.append([]) 

Answer 1

私はあなたがa_listとb_listを使用していることだと思う唯一の理由は、あなたがケースである必要はないボックスごとに2つのアイテムを、選択する必要が想定していることです。

私はあなたが単一のリストを使用し、どの項目が追加されたかを追跡するためにリストインデックスベースのアプローチを使うべきだと思います。

また、削除時に問題が発生するため、ループ中に削除の混乱を避けるために、-1に追加された項目を設定し、各パスの後にそれらをフィルタリングしてみてください。

ここではソリューションコードの共有に抵抗していますが、必要に応じてpingしてください。

Answer 2

リストを反復するときにリストを変更することは、常に挑戦です。ここでは、私が一般的に言及していないwhileループを使用する1つのソリューションがありますが、ここで問題なく動作するはずの簡単なアルゴリズムです。

whileループは、初期リストに要素が残っているかどうかをチェックします。次に、リストの最初の要素をポップ（削除して保存）し、リストの残りの部分を繰り返して、合計の条件を満たす追加の要素を検索します。ある要素が見つかった場合、それはサブリストに追加され、そのインデックスが記録されます。 forループの最後に、サブリストが出力リストに追加され、記録されたインデックスは、逆順でのが削除されます。

a_list = [9, 8, 6, 4, 3, 2, 2, 2] 
constraint = 10 

out = [] 
while a_list: 
    # grab first element of a_list and reset the list of 
    # to pop from a_list to pop from a_list 
    sub_out = [a_list.pop(0)] 
    pop_list = [] 

    for i,a in enumerate(a_list): 
     if a+sum(sub_out) <= constraint: 
      sub_out.append(a) 
      pop_list.append(i) 

    # append the sub_list to the output list 
    out.append(sub_out) 
    # remove each item in the pop_list in the reverse order 
    for i in reversed(pop_list): 
     a_list.pop(i) 

#output: 
>>> out 
[[9], [8, 2], [6, 4], [3, 2, 2]]