Galera...eu to fazendo um projeto da faculdade e me surgiu uma dúvida.
O projeto é pra desenvolver o problema da mochila binária. É um projeto sobre algoritmos gulosos.
O projeto é basicamente isso:
Imagina que temos uma mochila e queremos colocar os objetos (de um vetor) dentro da mochila. Os objetos podem ser colocados de 3 formas diferentes:
[list]Menor peso: os objetos mais leves são colocados primeiro;[/list]
[list]Maior valor: os objetos de maior valor são colocados primeiro ou[/list]
[list]Maior relação valor/peso: os objetos de maior relação valor por peso são colocados primeiro.[/list]
Tenho duas dúvidas.
[list]Como fazer a ordenação dos objetos de forma recursiva?[/list]/*
* Método de ordenação do menor para o maior PESO
*/
public static void ordenaMenorPeso(Objeto v[]) {
for (int i = v.length - 1; i >= 1; i--) {
for (int j = 1; j < i; j++) {
if (v[j - 1].getPeso() < v[j].getPeso()) {
Objeto aux = v[j];
v[j] = v[j - 1];
v[j - 1] = aux;
}
}
}
}
Como ordenar com duas regras de ordenação?[/list]
/* Este metodo deve implementar um algoritmo guloso que selecione objetos
* da listaDeObjetosDisponiveis a serem colocados na mochila de acordo
* com o criterio: 'objetos de menor peso primeiro', caso dois objetos
* tenham o mesmo peso, o criterio de desempate sera:
* 'objetos de maior valor primeiro' (apenas para os empates em peso).
*/
Não sei se essa implementação seria no mesmo método de ordenação.
Esse é o método que utiliza as ordenações. Esse é o do menor peso. Sabendo esse, os outros eu faço. A implementação dessa segunda regra é nesse método ou na ordenação mesmo?public static Mochila utilizaMenorPeso(double pesoMaximoDaMochila, Objeto[] listaDeObjetosDisponiveis) {
Mochila mochila = new Mochila(pesoMaximoDaMochila);
MetodosGulosos.ordenaMenorPeso(listaDeObjetosDisponiveis);
for (int i = 0; i < listaDeObjetosDisponiveis.length; i++) {
if (mochila.getPesoUsado() + listaDeObjetosDisponiveis[i].getPeso() <= mochila.getPesoMaximo()) {
mochila.setNumObjetosNaMochila(mochila.getNumObjetosNaMochila() + 1);
mochila.setPesoUsado(mochila.getPesoUsado() + listaDeObjetosDisponiveis[i].getPeso());
mochila.setValorDentroDaMochila(mochila.getValorDentroDaMochila() + listaDeObjetosDisponiveis[i].getValor());
}
}
