2

仕様が必要とする課題を完了しました:

  • 再帰的な解決策
  • 容量 <= 100
  • 値の長さ <= 25
  • パラメーターは容量とインデックスのみ
  • 値の繰り返しが許可されています

私はビンの梱包とナップザックの問題について何時間もかけて読んできました。

以下は機能しますが、非常に非効率的です。十数個の値でスタック オーバーフローが発生します。非常に非効率的で、拡張性がなく、どこから始めればよいかわかりません。

提案をいただければ幸いです。はい、これは学業の課題ですが、あきらめて B を獲得するよりも、問題を洗い流したほうがよいでしょう。

public void calculateCombinations(int capacity, int index) {
    count++;
    if(index < values.length) {
        if(values[index] <= capacity) {
            currentSolution.addLast(index);
            if(values[index] == capacity)
                flushSolution();
            else
                capacity -= values[index];
        }
        calculateCombinations(capacity, index + 1);
    } else
        if(currentSolution.peekLast() != null)
            calculateCombinations(capacity + values[currentSolution.peekLast()], currentSolution.removeLast() + 1);
}
4

1 に答える 1

3

ビンパッキング問題の重要なヒューリスティックは、常に最も厄介な（最大の）アイテムを最初にパッキングすることです。たとえば、移動するトラックを梱包する場合は、最初にピアノを入れてから、後で小さいものについて心配します。アイデアはあなたの柔軟性を最大化することです。

もう一つのテクニックは、私が「ブラケット」と呼んでいるものです。合計が50になる2つの数値を探していて、{2、3、9、18、24、29、37、45}のようなリストがあるとします。25を超えるまたは25未満の2つの値を持つことはできないため、すべての組み合わせをチェックする必要はありません。リストの両側の数値、つまり45 + 2、45 + 3、45 + 9、STOP、次の番号、37 + 2、37+3など。これは括弧です。ルールのセットを作成し、平均を囲むことにより、可能な組み合わせのごく一部をチェックするだけで済みます。

多くの場合、考えられるすべての組み合わせを列挙できないため、ビンパッキングは検索の問題です。チェスのようなものです。考えられるすべての動きを計算することはできません。良い動きを見つけようとしているだけです。

于 2013-02-26T22:45:16.500 に答える