Olá pessoal!
Estava trabalhando com algumas técnicas de algoritmos para resolver o problema da mochila 0/1 e uma das técnicas, Branch And Bound, foi traduzido a partir de um algoritmo matemático que abusa do uso de GOTOs. Sendo assim, gostaria que alguém verificasse o meu algoritmo para ver se é possível alterá-lo para funcionar sem os "continue", já que o seu uso não é lá muito aconselhado hoje em dia. O algoritmo é meio complexo e, por isso, talvez muitos não compreendam o que ele faz, mas não é preciso entender todos os detalhes para fazer o que estou pedindo.
Segue o algoritmo:
public static int[] branchAndBound( Item it[], int c ) {
java.util.Arrays.sort( it, new Item.ValuePerWeightComparator() );
int n = it.length;
Item[] items = new Item[ n+1 ];
System.arraycopy(it, 0, items, 0, n);
items[ n ] = new Item( 0, c+1 );
int[] xc = new int[n];
int[] x = new int[n];
int z=0, zc=0, cc=c, j=0, action=2;
while( true ) {
switch( action ) {
case 2: {
//2.[Compute UpperBound]
int r = items[j].getWeight(), i = j;
while(r <= cc) r += items[++i].getWeight();
r = i;
int pk=0, wk=0;
for( int k=j; k<r; k++ ) {
pk += items[k].getValue();
wk += items[k].getWeight();
}
int u = pk + ( (cc - wk) * items[r].getValue()/items[r].getWeight() );
if ( z >= zc+u ) {
action = 5; continue;
}
}
case 3: {
//3.[Perform a forward step]
while ( items[j].getWeight() <= cc ) {
cc -= items[j].getWeight();
zc += items[j].getValue();
xc[j] = 1;
j++;
}
if ( j <= n-1 ) {
xc[j] = 0;
j++;
}
if ( j < n-1 ) {
action = 2; continue;
} else if ( j == n-1 ) {
action = 3; continue;
}
}
case 4: {
//[4. Update the best solution so far]
if ( zc > z ) {
z = zc;
for( int k=0; k<n; k++ ) x[k] = xc[k];
}
j = n-1;
if ( xc[n-1] == 1 ) {
cc += items[n-1].getWeight();
zc -= items[n-1].getValue();
xc[n-1] = 0;
}
}
case 5: {
//5.[Backtrack]
int i;
for( i=j-1; i>=0 && xc[i]!=1; i-- );
if (i > -1) {
cc += items[i].getWeight();
zc -= items[i].getValue();
xc[i] = 0;
j = i+1;
action = 2; continue;
}
return x;
}
}
}
}
Um dos parâmetros do método acima é a instância da classe Item, segue o código dessa classe também>
public class Item {
private int value;
private int weight;
public Item() {
this(1,1);
}
public Item( int value, int weight ) {
setValue( value );
setWeight(weight);
}
public void setValue( int value ) {
this.value = value;
}
public int getValue() {
return value;
}
public void setWeight( int weight ) {
this.weight = weight;
}
public int getWeight() {
return weight;
}
public String toString() {
return "v=" + this.getValue() + "_" + "w=" + this.getWeight();
}
static class ValueComparator implements java.util.Comparator<Item> {
public int compare( Item i1, Item i2 ) {
int v1 = i1.getValue();
int v2 = i2.getValue();
if ( v1 == v2 )
return 0;
else if ( v1 < v2 )
return 1;
else
return -1;
}
}
static class WeightComparator implements java.util.Comparator<Item> {
public int compare( Item i1, Item i2 ) {
int w1 = i1.getValue();
int w2 = i2.getValue();
if ( w1 == w2 )
return 0;
else if ( w1 > w2 )
return 1;
else
return -1;
}
}
static class ValuePerWeightComparator implements java.util.Comparator<Item> {
public int compare( Item i1, Item i2 ) {
float r1 = (float)i1.value / i1.weight;
float r2 = (float)i2.value / i2.weight;
if (r1 == r2)
return 0;
else if (r1 > r2)
return -1;
else
return 1;
}
}
}