Backpack.java

import java.util.Arrays;
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 final boolean[] currentSolution;
    private final boolean[] bestSolution;
    private int nodesExplored = 0;

    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 : " + Arrays.toString(bestSolution));
        System.out.println("Nombre de nœuds explorés : " + nodesExplored);
    }

    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) {
        nodesExplored++;
        // Si on a exploré tous les objets
        if (index >= loots.size()) {
            if (currentValue > bestValue) {
                bestValue = currentValue;
                System.arraycopy(currentSolution, 0, bestSolution, 0, loots.size());
            }