Backpack.java

import java.util.Comparator;
import java.util.List;

public class Backpack {
    private final int capacity;
    private final List<Loot> loots;
    private int bestValue = 0;
    private int currentWeight = 0;
    private int currentValue = 0;
    private boolean[] currentSolution;
    private boolean[] bestSolution;

    public Backpack(int capacity, List<Loot> loots) {
        this.capacity = capacity;
        this.loots = loots;
        this.currentSolution = new boolean[loots.size()];
        this.bestSolution = new boolean[loots.size()];
    }

    public void solve() {
        this.sortByRatio();
        explore_from(0);
        System.out.println("La valeur optimale est : " + bestValue);
        System.out.println("Objets inclus dans la solution optimale : " + bestSolution);

    }

    public String toString(){
        return capacity +"\n"+loots;
    }

    /**
    Méthode pour trier les objets par ordre décroissant selon leur ratio
    */
    public void sortByRatio(){
        loots.sort(Comparator.comparing(Loot::getRatio).reversed());
    }

    public int solutionFractionnelle(int startIndex, int remainingCapacity) {
        int sfValuee = 0;
        int sfWeight = 0;

        // On commence à partir de startIndex
        for(int i = startIndex; i < loots.size(); i++) {
            Loot loot = loots.get(i);
            if(sfWeight + loot.getWeight() <= remainingCapacity){
                // Si l'objet entier peut entrer dans le sac
                sfValuee += loot.getValue();
                sfWeight += loot.getWeight();
            }
            else {
                // Si l'objet ne peut pas entrer entièrement dans le sac
                int remainingWeight = remainingCapacity - sfWeight;
                sfValuee += (int) (loot.getRatio() * remainingWeight);
                break;
            }
        }
        return sfValuee;
    }

    private void explore_from(int index) {
        // Si on a exploré tous les objets
        if (index >= loots.size()) {
            if (currentValue > bestValue) {
                bestValue = currentValue;
                System.arraycopy(currentSolution, 0, bestSolution, 0, loots.size());
            }
            return;
        }

        // On calcule la borne supérieure pour ce nœud
        int remainingCapacity = capacity - currentWeight;
        int borneSuperieure = currentValue + solutionFractionnelle(index, remainingCapacity);

        // Si la borne supérieure est inférieure à la meilleure solution
        if (borneSuperieure <= bestValue) {
            return;
        }

        // on essaye d'explorer avec l'objet
        Loot currentLoot = loots.get(index);
        if (currentWeight + currentLoot.getWeight() <= capacity) {
            currentWeight += currentLoot.getWeight();
            currentValue += currentLoot.getValue();
            currentSolution[index] = true;
            explore_from(index + 1);
            currentWeight -= currentLoot.getWeight();
            currentValue -= currentLoot.getValue();
            currentSolution[index] = false;
        }

        // on explore sans l'objet
        explore_from(index + 1);
    }

    public int getBestValue() {
        return bestValue;
    }

    public boolean[] getBestSolution() {
        return bestSolution;
    }
}