Skip to content
Snippets Groups Projects
Select Git revision
  • d6f0f60e3127f95eaceb32d425fe72e032dd2b4d
  • master default protected
2 results

App.java

Blame
  • Forked from SAYEH Nahlane ghina / graphic-2020..
    Source project has a limited visibility.
    Code owners
    Assign users and groups as approvers for specific file changes. Learn more.
    BackPackSolver.java 1.58 KiB
    package fr.univamu.progav.td2;
    
    import java.util.ArrayList;
    import java.util.List;
    
    public class BackPackSolver {
    
    
    
      private final List<Item> allItems;
      private final List<Item> currentBackpack = new ArrayList<>();
      private final int availableVolume;
    
      public BackPackSolver(List<Item> allItems, int availableVolume) {
        this.allItems = allItems;
        this.availableVolume = availableVolume;
      }
    
    
      public List<Item> findBestValueBackpack(int nextItemIndex) {
        if (nextItemIndex >= allItems.size()) {
          return new ArrayList<>(currentBackpack);
        }
        List<Item> backpack1 = findBestValueBackpack(nextItemIndex+1);
        int currentVolume = sumVolumes(currentBackpack);
        if (currentVolume + allItems.get(nextItemIndex).volume > availableVolume) {
          return backpack1;
        }
        currentBackpack.add(allItems.get(nextItemIndex));
        List<Item> backpack2 = findBestValueBackpack(nextItemIndex+1);
        return selectBestBackpack(backpack1, backpack2);
      }
    
    
    
      private List<Item> selectBestBackpack(List<Item> backpack1, List<Item> backpack2) {
        int value1 = sumValues(backpack1);
        int value2 = sumValues(backpack2);
        return (value1 >= value2)? backpack1 : backpack2;
      }
    
      public record Item(String name,int volume, int value) {
        @Override
        public String toString() {
          return name + " (Volume=" + volume + ", value=" + value + ")";
        }
      }
    
      private static int sumValues(List<Item> backpack1) {
        return backpack1.stream().mapToInt(Item::value).sum();
      }
    
      private int sumVolumes(List<Item> backpack) {
        return backpack.stream().mapToInt(Item::volume).sum();
      }
    
    }