0

質問:
整数の重みのリストが与えられました。これらの重みを 2 つのセットに分散して、各セットの合計重量の差ができるだけ小さくなるようにする必要があります。
入力データ: 重みのリスト。
出力データ: 重量差の最小値を表す数値。

答えを見ましたが、なぜ bes​​tval = -1 なのか理解できません。誰でも私がそれを理解するのを助けることができますか? どうもありがとう！
コードは次のとおりです。

import itertools;

def checkio(stones):

    total = 0
    for cur in stones:
        total += cur

    bestval = -1

    for i in range(0,len(stones)):
        for comb in itertools.combinations(stones,i):
            weight = 0
            for item in comb:
                weight += item
            d = diff(total - weight, weight)
            if bestval == -1 or d < bestval:
                bestval = d                    
    return bestval

def diff(a,b):
    if a >= b:
        return a - b
    else:
        return b - a
4

4 に答える 4

2

これは正しいとは限らないことがわかっている開始値であるため、どんなに悪くても最初の回答に置き換えられます。

于 2013-06-26T14:45:37.730 に答える
1

bestvalは最初に -1 に設定され、最初のループで に更新されdます。その後、は、現在の よりも良い値 (つまり、重みの差が小さい) になるbestvalたびに再度更新されます。dbestval

キーコードはこちら...

if bestval == -1 or d < bestval:
    bestval = d

したがって、ループの最初のパスでbestval == -1は true であり、bestval更新されます。その後、d < bestvalチェックは値を更新するかどうかを決定します。

于 2013-06-26T14:46:06.527 に答える
0

すべての組み合わせを試すのは力ずくで、問題を解決するのに時間のかかる方法だと思います。

おもりをサイズごとに並べ替え、重いものから軽いものへと、重みの違いに応じて左右の山に 1 つずつ追加すると、おそらく最良の答えが得られます。

以下の疑似コードで、O(n) 問題になります (並べ替えが無視された場合)。

sort weights into stack;
while (weight = pop stack) {
  if (sum(left) - sum(right) > 0) push weight on right
  else push weight to left;
}
bestval = sum(left) - sum(right);

例: { 1, 2, 3, 4}

0. l 0 r 0 => 0 add 4 to left
1. l 4 r 0 => +4 add 3 to right
2. l 4 r 3 => +1 add 2 to right
3. l 4 r 5 => -1, add 1 to left
4. l 5 r 5 => same
于 2013-06-26T15:01:40.313 に答える
0

貪欲なアルゴリズムは、IS が優れたヒューリスティックであることを示唆していますが、最善の解決策が得られる保証はありません。この問題は NP 困難です。ローカル検索 (シミュレートされたアニーリングなど) を使用して確率論的に "解決" することができます。ここで、解決策は "良い" 答えを意味します: 最適に近いと信じられているものです。Knuth は、40 個の重さと 3 つの瓶 (重さは 1..40 の平方根に等しい) について、この問題を提案しました。

ジェリー

于 2013-06-26T19:13:25.980 に答える