Backpack.java

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

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

    public Backpack(int capacity, List<Loot> loots) {
        this.capacity = capacity;
        this.loots = loots;
    }

    public void solve() {
        bestSolution = new boolean[loots.size()];
        currentSolution = new boolean[loots.size()];
        sortByRatio();
        solutionFractionnelle();
        explore_from(0);
    }

    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 void solutionFractionnelle(){
        this.sortByRatio();

        for(Loot loot : loots){
            if(sfWeight + loot.getWeight() <= this.capacity){
                // 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 = this.capacity - sfWeight;
                sfValuee += (int) (loot.getRatio() * remainingWeight);
                break;
            }
        }
    }

    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;
        }

        // Si la valeur actuelle + la valeur restante possible (sfValuee - valeur déjà utilisée)
        // est inférieure à la meilleure solution, on coupe la branche
        if (currentValue + (sfValuee - currentValue) <= bestValue) {
            return;
        }

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

        // Branche droite - sans l'objet
        explore_from(index + 1);
    }

    public int getSfValuee() {
        return sfValuee;
    }

    public int getBestValue() {
        return bestValue;
    }
}