11

セットは以下のこのメソッドに渡され、バーの長さも渡されます。セットからの特定の数値がバーの長さから削除された場合、ソリューションはセットから最小量の無駄を与える数値を出力する必要があります。したがって、バーの長さは 10、セットには 6、1、4 が含まれているため、解は 6 と 4 であり、無駄は 0 です。セットをバックトラックする条件に問題があります。また、無駄な「グローバル」変数を使用してバックトラッキングの側面を支援しようとしましたが、役に立ちませんでした。

SetInt は手動で作成されたセットの実装であり、追加、削除、セットが空かどうかのチェック、およびセットから最小値を返すことができます。

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package recback;


public class RecBack {

   public static int WASTAGE = 10;

    public static void main(String[] args) {



         int[] nums = {6,1,4};
        //Order Numbers

        int barLength = 10;
        //Bar length

        SetInt possibleOrders = new SetInt(nums.length);
        SetInt solution = new SetInt(nums.length);
        //Set Declarration


        for (int i = 0; i < nums.length; i++)possibleOrders.add(nums[i]);
        //Populate Set

        SetInt result = tryCutting(possibleOrders, solution, barLength);
        result.printNumbers();


    }

    private static SetInt tryCutting(SetInt possibleOrders, SetInt solution, int lengthleft)
      {



        SetInt clonedSet = possibleOrders.cloneSet(); //initialise selection of candidates

        for (int i = 0; i < possibleOrders.numberInSet(); i++) // the repeat
          {

            int a = clonedSet.min(); //select next candidate

            if (a <= lengthleft) //if accecptable
              { 
                solution.add(a); //record candidate
                lengthleft -= a;
                clonedSet.remove(a); //remove from original set

                if (!clonedSet.isEmpty()) //solution not complete
                  {
                    WASTAGE +=a;
                    tryCutting(clonedSet, solution, lengthleft);//try recursive call

                    if (lengthleft > WASTAGE)//if not successfull
                      {
                        WASTAGE += a;
                        solution.remove(a);
                      }

                  } //solution not complete
              }
          } //for loop
        return solution;

      }
  }
4

2 に答える 2

1

いくつかの問題があります。

1つはこの行です： int a = clonedSet.min(); //select next candidate

例を見ていくと、値 1 が見つかり、それが最初に使用されるため、1 と 4 が使用されますが、6 は使用されません。

<=残りの長さになる最大値を探している方が良いでしょう。

この行も私には奇妙です：

WASTAGE +=a;

減算する必要があると思いますが、なぜ静的整数を変更しているのですか?

これが変更可能なものである場合は、それを渡し、無駄になった量が終わったら返す必要があります。そのため、返す新しいクラス、ソリューション、および無駄になった量を用意してください。

再帰の場合は、例を用意してから、一度に 1 つずつ見ていき、その動作が期待どおりかどうかを確認します。

このループを見たいと思うかもしれません:

for (int i = 0; i < possibleOrders.numberInSet(); i++) // the repeat

これを再帰的に実行している場合、3 つの可能な解決策がある場合、3 回実行するのではなく、最終的に 6 回のテストを実行することになると思います。

for ループを削除しても問題ありません。毎回それが通過するのを見ることができるように、印刷ステートメントを入れてください。

アップデート：

より多くの情報に基づいて、考えられるすべてのソリューションを収集し、最初のパスを実行して、そのように機能するソリューションを取得することができます。次に、可能な解決策を左または右にシフトしてから、もう一度試してください。

すべての方法でシフトした場合、さまざまな組み合わせを試しましたが、可能なすべての組み合わせではありませんが、それらのソリューションを使用して、どれが最適かを確認できます。

より多くの組み合わせをテストしたい場合は、アイテムを削除するまでループする必要があり、これは再帰的である可能性があります。

したがって、再帰関数の中に別の関数が必要になるため、考えられるすべての組み合わせを再帰的に調べてから、問題の解決策を再帰的に探します。

を探すのmaxがおそらくベストだと思いますが、それは私の直感であり、それminがベストであることを示すことができます。

于 2011-04-15T18:17:04.553 に答える
0

ジェームズに同意します。ループは必要ありません/したくありません。私が理解しているように、「tryCutting」アルゴリズムは、可能な順序のリスト、検討中の現在のソリューション、および現在のソリューションをカットした場合の残りの長さを取ります。次に、次のことを行う必要があります。

  • 注文から最短カットを削除します。残りの長さよりも長い場合は、それ以上試さないでください。さもないと、
  • 最初のケース: そのカットを満たしていない - 注文の新しいリストと同じ現在の長さで再度カットを試みます
  • 2 番目のケース: あなたはそのカットを満たします。それを現在のソリューションに追加し、注文の新しいリストとそのカットによって短縮された長さでカットを試みます。最後に、現在のソリューションから再び外します (バックトラック用)。
  • 注文を最短カットバックする (バックトラッキング用)

ここで、試行するケースごとに、これまでのグローバル ベスト ケースに対して残っている長さを確認します。現在のソリューション (のクローン) でグローバルを更新するよりも短いです。

これにより、単一の最適なソリューション、または同等に優れたソリューションが複数ある場合はそのうちの 1 つが得られます。すべてのソリューションを取得するには、SetInts のグローバル リストが必要です。現在のソリューションよりも優れたソリューションが見つかった場合は、リストをクリアして新しいソリューションを追加します。それが現在のベストと等しい場合は、それを追加するだけです.

ここにコードがあります： 

public static void main(String[] args) {
    int[] nums = {6,1,4};          //Order Numbers
    int barLength = 10;         //Bar length
    bestSolution = new HashSet<SetInt>();
    bestWastage = barLength;
    SetInt possibleOrders = new SetInt(nums.length);
    SetInt solution = new SetInt(nums.length);         //Set Declarration
    for (int i = 0; i < nums.length; i++) {
        possibleOrders.add(nums[i]);         //Populate Set
    }
    tryCutting(possibleOrders, solution, barLength);
    for (SetInt result : bestSolution) {
        result.printNumbers();
    }

}

private static int bestWastage;
private static Set<SetInt> bestSolution;

private static void tryCutting(SetInt possibleOrders, SetInt solution, int lengthleft) {
    if (lengthleft < bestWastage) {
        // Better than the best solution
        bestWastage = lengthleft;
        bestSolution.clear();
        bestSolution.add(solution.cloneSet());
    } else if (lengthleft == bestWastage) {
        // Just as good as the best solution
        bestSolution.add(solution.cloneSet());
    }
    int a = possibleOrders.min(); //select next candidate
    if (a <= lengthleft) { // If acceptable
        possibleOrders.remove(a); // Remove it
        tryCutting(possibleOrders, solution, lengthleft); // Try without that cut
        solution.add(a); // add to the solution
        tryCutting(possibleOrders, solution, lengthleft - a); // Try with that cut
        solution.remove(a); // remove again
        possibleOrders.add(a); // add the candidate back on again
    }
}
于 2011-04-21T10:58:59.433 に答える