-3

私はこの問題を抱えています：「重量が1kgから10kgまで変化するn個のアイテムが与えられた場合、それぞれが10kgを超えない可能性があることを知って、それらを最小量のバッグにどのように分配しますか.」.

重さの大きいものから軽いものへと並べ替え、収まる場合は袋に入れ、入らない場合は新しい袋を作成することで解決しようとしました。その場合は、残りのアイテムの中で最も重いものから最も軽いものへとやり直してください。これが私のコードです：

list_of_items=raw_input("Input the items' weights (separated by spaces): ").split()

for i in range(len(list_of_items)):
        list_of_items[i]=int(list_of_items[i])

list_of_items.sort()
list_of_items.reverse()

while list_of_items[0]>=10:
        list_of_items=raw_input("You have input an item wheighing over 10kg: ").split()
        for i in range(len(list_of_items)):
                list_of_items[i]=int(list_of_items[i])

        list_of_items.sort()
        list_of_items.reverse()

set_of_bags=[] #In this list we'll store the bags

while(len(list_of_items)!=0):

        weight=0
        bag=[] #creates a new bag

        for item in list_of_items: #cycle copies items to bag
                if item+weight<=10:
                        bag.append(item)
                        weight+=item
        set_of_bags.append(bag) #adds bag to set_of_bags

        for item in bag: #deletes the items that have been put in set_of_bags from original list
                list_of_items.remove(item)

# output
n=0
for bag in set_of_bags:
        n+=1
        weight=0
        for j in bag:
                weight += j
        print "bag #"+str(n), bag, "=>", weight, "kg."

これで正しい答えが得られると思いますが、それを証明する方法がわかりません。何か助けはありますか？

4

2 に答える 2

1

もちろん、これは最適ではありません。一般に、何かを並べ替えてから「貪欲なアプローチ」を使用する、つまり最小または最大のものを選択する自明でないアルゴリズムがあり、これが正しい理由がわからない場合、それはおそらく間違っています。特に整数の最適化問題がある場合。

たとえば、 がある場合3, 3, 3, 3, 4, 4、アルゴリズムは 2 つではなく 3 つのバッグを使用することになります。

あなたのアルゴリズム:

Bag 1: 4, 4
Bag 2: 3, 3, 3
Bag 3: 3

最適な：

Bag 1: 4, 3, 3
Bag 2: 4, 3, 3

ここで、他のいくつかのヒューリスティックも同様に間違っていることを示すために、次の例を見てください3, 3, 4, 6, 7, 7。低い方から高い方に向かって3, 3, 41つの袋に入れると、3つではなく4つの袋になります。同じ例は、1 つのバッグを完全に満たすことができるからといって、そうすべきではないことを示しています。7(ただし、とのように 2 つのアイテムを組み合わせてバッグを満たす3場合は、それらをバッグに入れて完全に忘れることができます。)

最後に を見てください3, 3, 3, 3, 4, 4, 4, 4。低い方から行くと、次の 4 つのバッグが得られます。

Bag 1: 3 3 3
Bag 2: 3 4
Bag 3: 4 4
Bag 4: 4

高い方から行くと、次の 4 つの袋が得られます。

Bag 1: 4 4
Bag 2: 4 4
Bag 3: 3 3 3
Bag 4: 3

ただし、次の 3 つのバッグを取得できます。

Bag 1: 4 3 3
Bag 2: 4 3 3
Bag 3: 4 4

できることは次のとおりです (証明は省略します)。

  • 10の場合は、別の袋に入れてください。最初にすべての 10 を処理します。
  • 9 を持っている場合は、可能であれば 1 と一緒にバッグに入れるか、単独で入れます。続行する前にすべての 9 に対処します。
  • 8 を持っている場合は、可能であれば 2、可能であれば 1 を 2 つ、可能であれば 1 を 1 つ、または単独でバッグに入れます。続行する前にすべての 8 に対処します。
  • 7 があれば 3 と一緒に袋に入れ、そうでない場合は 2 と 1 を、そうでない場合は 2 を 1 つ、そうでない場合は 1 を残した数だけ袋に入れます。続行する前にすべての 7 に対処してください。
  • あなたが6を持っているなら、4を持っているなら入れてください。
  • この時点で残っているのは、6 秒、5 秒、3 秒、2 秒、1 秒です。さて、1 は重要ではありません。それらを削除し、最適なソリューションを見つけて、それらを元に戻すことができます。また、5が2つ以上ある場合は、それらを足して袋を作ります（証明も簡単です）。したがって、6、3、2、および最大 1 つの 5 があります。5 がある場合は、可能であれば 3 を使用し、次に 2 または残りの 1 を使用する必要があります。3 がない場合は、残りの 2 と同じ数の 5 を使用し、次に 1 を使用する必要があります。
  • これで 6 秒、3 秒、2 秒が残りました。今は単純なゲームのようです。実際には 2 と 3 しかありません。それが重要です。「6」ごとに、「3」を 1 つまたは「2」を 2 つ取ることができます。6 がなくなったら、5 つの 2、または 3 と 3 つの 2、または 2 つの 3 と 2 つの 2、または 3 つの 3 を取ることができます。これで、動的計画法を使用して最適解を見つけることができます。たとえば、2s、3s、および6sd[i, j, k]のバッグの最小数をとします。より良い解決策があるかもしれません。ijk
于 2013-10-08T19:18:41.757 に答える
0

これは近いと思いますが、順序が狂っている可能性のある重量を考慮しているとは思いません.9kg、5kg、1kgのアイテムがあるようです. 9kg の商品を追加すると、1kg の商品が収まる場合でも、5kg が多すぎることがわかり、次のバッグにスキップします。

私はPythonの最適化についてはほとんど知りませんが、最速だと思います。

生の値を取得します (10KG、5KG、8KG、2KG、2KG、1KG、10KG、9KG); ソート/インデックス重量量 (10KG:2、9KG:1、8KG:1、5KG:1、2KG:2、1KG:1)

最初に最も重い値でバッグの充填を開始し、重量が超過した場合は、値インデックスの最後でバッグが A: フルまたは B: になるまで、次に大きなインデックスを追加しようとします。

値の数によっては...値のインデックスを逆方向に検索し、次に高い値に対してテストする方が実際には高速である可能性があります。これにより、より大きなアイテムに対して多くの値を反復する必要がなくなります。(たとえば、10KG は 1KG をテストして動作しないことを確認します。9KG は 1KG をテストして動作することを確認しますが、2KG をテストして動作しないことを確認します。したがって、1KG を最良の値として使用します。 8, 5, 2 ,1 から移動するのに 4 回かかるのではなく、2 回の反復)。

これが理にかなっていることを願っています。

于 2013-10-08T19:01:37.297 に答える