次のようなプログラムを作っています
一つ、または二つ以上の升がある
それぞれの升には、すでに水が入っている
これらの升を使って、目的の水の量を測る
例1
升1(容量3l)、実際に入っている水の量は2l
升2(容量1l)、実際に入っている水の量は0l
目的の水の量は1l
⇒升1の水を升2に移すと、
升1: 2l ⇒1l
升2: 0l ⇒1l
完成
例2
升1(容量3l)、実際に入っている水の量は0l
升2(容量3l)、実際に入っている水の量は0l
升3(容量3l)、実際に入っている水の量は0l
目的の水の量は5l
⇒解なし
例3
升1(容量0l)、実際に入っている水の量は0l
目的の水の量は0l
⇒既に解けている
実際のプログラムはこんな感じ
public class Masu {
private int[] masu;
private int[] state;
public Wein(int[] masu, int[] state) {
this.masu = masu; //升1(容量3l),升2(容量0l)→masu[0] = 3; masu[1] = 0;
this.state = state; //升1,実際の水1l→state[0] = 1;
}
public boolean solved(int purpose, int[] result){
for(int i=0; i<masu.length; i++)
if(result[i]==purpose)
return true;
return false;
}
//To Do
public void solveHelper(int purpose, int from, int to, int[] result){//バックトラック法
if(solved(purpose, from, to, result))
return;
//移さない
result[from] = state[from];
result[to] = state[to];
solveHelper(from,to+1,result);
solveHelper(from+1,to,result);
//移す
if(state[from]>masu[to]-state[to]){
int d = state[from]-(masu[to]-state[to]);
result[from] = d;
result[to] = masu[to];
}
else{
result[from] = 0;
result[to] = state[to] + state[from]
}
solveHelper(from,to+1,result[][]);
solveHelper(from+1,to,result[][]);
return;
}
//To Do
public int[] solve(int purpose){//purpose=目的の水の量
int[] result = new int[masu.length];
//result[1] = 問題を解いた後に升2に入っている水の量
solveHelper(purpose, result);
return result;
}
}
水を移すか移さないかで再帰をすれば、バックトラック法を作れると思ったのですが、バックトラック法だと、同じ作業を繰り返さないのでダメな気がしてきました…
例えば、升1から升2に移して升2から升3に移したあとに、また升1から升2に移す作業を、バックトラック法では試してくれないですよね？そうすると、すべてのパターンを試すことができないのでは…
そもそもバックトラック法を使ってプログラムしようとしてるのが間違ってるのかも…