Solving the Knapsack Problem in Java: Greedy Approach with Code Example
Solving the Knapsack Problem in Java
public class ProblemaMochila {
public ProblemaMochila() {
}
public ArrayList<ItemRoubo> resolver(ArrayList<ItemRoubo> totalItems, int max_items, int peso_max) {
ArrayList<ItemRoubo> mochila = new ArrayList<ItemRoubo>(max_items);
Collections.sort(totalItems);
double pesoMochila = 0;
int posicao = 0;
while (pesoMochila < peso_max && posicao < totalItems.size()) {
ItemRoubo tmp = totalItems.get(posicao);
if (pesoMochila + tmp.getPeso() <= peso_max) {
mochila.add(tmp);
pesoMochila += tmp.getPeso();
}
posicao++;
}
return mochila;
}
}
Main Class
public class Main {
public static void main(String[] args) {
ProblemaMochila pbM = new ProblemaMochila();
ArrayList<ItemRoubo> totalItems = new ArrayList<ItemRoubo>();
totalItems.add(new ItemRoubo(10, 60));
totalItems.add(new ItemRoubo(20, 100));
totalItems.add(new ItemRoubo(30, 120));
ArrayList<ItemRoubo> itensRoubados = pbM.resolver(totalItems, 200, 50);
for (ItemRoubo itemRoubo : itensRoubados) {
System.out.println(itemRoubo);
}
}
}
Item Class
public class ItemRoubo implements Comparable<ItemRoubo> {
private double peso; //exemplo 6 kg
private double valorTotal; //exemplo 60
public ItemRoubo(double peso, double valorTotal) {
this.peso = peso;
this.valorTotal = valorTotal;
}
Getters and Setters
@Override
public int compareTo(ItemRoubo outroItem) {
if (this.valorTotal < outroItem.valorTotal) {
return -1;
}
if (this.valorTotal > outroItem.valorTotal) {
return 1;
}
return 0;
}
@Override
public String toString() {
return