皆さん、最近私のアルゴリズムの問題について投稿しました。
コードを少し修正したので、ある程度バックトラックするようになりましたが、出力にはまだ欠陥があります。私はこれをかなりデバッグして、すべての変数値をチェックしましたが、問題を見つけられないようです。
ここでも、完全な解決策ではなく、アドバイスが非常に役立ちます。私のコードにはいくつかの問題があるだけだと思いますが、どこにあるのかわかりません。
//前回の投稿より:
基本的に、セットは以下のこのメソッドに渡され、バーの長さも渡されます。ソリューションは、セットからの特定の数値がバーの長さから削除された場合に最小量の無駄を与えるセットからの数値を出力する必要があります。したがって、バーの長さは 10、セットには 6、1、4 が含まれているため、解は 6 と 4 であり、無駄は 0 です。セットをバックトラックする条件に問題があります。また、無駄な「グローバル」変数を使用してバックトラッキングの側面を支援しようとしましたが、役に立ちませんでした。
SetInt は手動で作成されたセットの実装であり、追加、削除、セットが空かどうかのチェック、およびセットから最小値を返すことができます。
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package recursivebacktracking;
/**
*
* @author User
*/
public class RecBack {
int WASTAGE = 10;
int BESTWASTAGE;
int BARLENGTH = 10;
public void work()
{
int[] nums = {6,1,2,5};
//Order Numbers
SetInt ORDERS = new SetInt(nums.length);
SetInt BESTSET = new SetInt(nums.length);
SetInt SOLUTION = new SetInt(nums.length);
//Set Declarration
for (int item : nums)ORDERS.add(item);
//Populate Set
SetInt result = tryCutting(ORDERS, SOLUTION, BARLENGTH, WASTAGE);
result.printNumbers();
}
public SetInt tryCutting(SetInt possibleOrders, SetInt solution, int lengthleft, int waste)
{
for (int i = 0; i < possibleOrders.numberInSet(); i++) // the repeat
{
int a = possibleOrders.min(); //select next candidate
System.out.println(a);
if (a <= lengthleft) //if accecptable
{
solution.add(a); //record candidate
lengthleft -= a;
WASTAGE = lengthleft;
possibleOrders.remove(a); //remove from original set
if (!possibleOrders.isEmpty()) //solution not complete
{
System.out.println("this time");
tryCutting(possibleOrders, solution, lengthleft, waste);//try recursive call
BESTWASTAGE = WASTAGE;
if ( BESTWASTAGE <= WASTAGE )//if not successfull
{
lengthleft += a;
solution.remove(a);
System.out.println("never happens");
}
} //solution not complete
}
} //for loop
return solution;
}
}