Aujourd’hui je vais vous parler de la dernière édition de la BattleDev. Les plus assidus d’entre vous objecteront que je l’ai déjà fait la semaine dernière. C’est pas faux, mais aujourd’hui je vais parler plus particulièrement de l’exercice 4, exercice qui consiste à remplir une lampe à huile avec de la poudre de perlimpinpin.

Comme je suis sympa je vous redonne l’énoncé original :

Vous glissez malencontreusement avec vos babouches sur votre tapis volant et tombez à travers des sables mouvants dans une caverne magique où se trouve un fabuleux trésor.
Le trésor est composé de différentes épices et poudres plus précieuses les unes que les autres dont on vous donne le prix au kilogramme ainsi que la quantité totale de chacune des poudres contenues dans la caverne. Le trésor comporte également des pierres précieuses, chacune a un poids et une valeur indivisible. Vous n’avez avec vous qu’une vieille lampe à huile de contenance finie (vous avez cru quoi ? ce n’est pas magique hein !) et vous devez indiquer quelles poudres et pierres précieuses emporter dedans pour maximiser la valeur du trésor que vous allez rapporter à la surface (avide que vous êtes) !
https://www.isograd.com/FR/solutionconcours.php?contest_id=49&que_str_id=®_typ_id=2

Pour résoudre ce problème il va falloir construire une liste avec les différents éléments disponibles et la trier par prix au kilo.

Des classes pour nos entités

On commence donc par définir des classes pour ces éléments.

Tout d’abord une interface :

private interface Item extends Comparable<Item> {

  float getPricePerKilo();

  int getWeight();

  boolean isSplittable();
}

Puis une première implémentation pour les pierres précieuses :

private static class Jewel implements Item {
  private final float pricePerKilo;
  private final int weight;

  public Jewel(float totalPrice, int weight) {
    this.pricePerKilo = totalPrice / weight;
    this.weight = weight;
  }

  @Override
  public String toString() {
    return "Jewel{" +
            "pricePerKilo=" + pricePerKilo +
            ", weight=" + weight +
            '}';
  }

  @Override
  public int compareTo(Item other) {
    return Float.compare(other.getPricePerKilo(),this.pricePerKilo);
  }

  @Override
  public float getPricePerKilo() {
    return this.pricePerKilo;
  }

  @Override
  public int getWeight() {
    return this.weight;
  }

  @Override
  public boolean isSplittable() {
    return false;
  }
}

Et une deuxième implémentation pour les épices :

private static class Spice implements Item {
  private final float pricePerKilo;
  private final int weight;

  public Spice(float pricePerKilo, int weight) {
    this.pricePerKilo = pricePerKilo;
    this.weight = weight;
  }

  @Override
  public String toString() {
    return "Spice{" +
            "pricePerKilo=" + pricePerKilo +
            ", weight=" + weight +
            '}';
  }

  @Override
  public int compareTo(Item other) {
    return Float.compare(other.getPricePerKilo(),this.pricePerKilo);
  }

  @Override
  public float getPricePerKilo() {
    return this.pricePerKilo;
  }

  @Override
  public int getWeight() {
    return this.weight;
  }

  @Override
  public boolean isSplittable() {
    return true;
  }
}

Enfin on définit une classe pour la solution du problème :

private static class Solution {
  private final List<Item> items = new ArrayList<>();

  public int getWeight() {
    int weight = 0;
    for (Item item : items) {
      weight += item.getWeight();
    }
    return weight;
  }

  public int getPrice() {
    int price = 0;
    for (Item item : items) {
      price += (item.getWeight() * item.getPricePerKilo());
    }
    return price;
  }

  public void addItem(Item item) {
    items.add(item);
  }


  @Override
  public String toString() {
    return "Solution{" +
            "items=" + items +
            ", price=" + getPrice() +
            ", weight=" + getWeight() +
            '}';
  }
}

Place à l’algorithme

On peut maintenant écrire la méthode principale :

package com.jbleduigou;

import java.io.ByteArrayInputStream;
import java.io.InputStream;
import java.nio.charset.StandardCharsets;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class PerlimpinpinSimple {
  
  public static void main(String[] args) {  
    solveProblem(System.in);
  }

  public static void solveProblem(InputStream inputStream) {
    // First read input data
    String line;
    Scanner sc = new Scanner(inputStream);
    int nbJewels = -1;
    int maxWeight = -1;
    List<Item> items = new ArrayList<>();
    int lineNumber = 0;
    while (sc.hasNextLine()) {
      line = sc.nextLine();
      if (nbJewels == -1) {
        //Reading first line
        nbJewels = Integer.parseInt(line.split(" ", 0)[0]);
        maxWeight = Integer.parseInt(line.split(" ", 0)[2]);
        System.err.println("Max weight="+maxWeight);
      } else {
        int weight = Integer.parseInt(line.split(" ", 0)[1]);
        if (lineNumber <= nbJewels) {
          //Reading a line describing a Jewel
          float totalPrice = Float.parseFloat(line.split(" ", 0)[0]);
          items.add(new Jewel(totalPrice, weight));
        } else {
          //Reading a line describing a Spice
          float pricePerKilo = Float.parseFloat(line.split(" ", 0)[0]);
          items.add(new Spice(pricePerKilo, weight));
        }
      }
      lineNumber++;
    }
    // Data has been read, printing it for debug purposes
    Collections.sort(items);
    System.err.println(items);
    // Find best solution
    Solution solution = findSolution(maxWeight, items);
    // Output result
    System.err.println(solution);
    System.out.println(solution.getPrice());
  }

  private static Solution findSolution(int maxWeight, List<Item> items) {
    Solution solution = new Solution();
    for (Item item : items) {
      if (solution.getWeight() + item.getWeight() <= maxWeight) {
        solution.addItem(item);
      } else {
        if (item.isSplittable()) {
          int remaining = maxWeight - solution.getWeight();
          if (remaining > 0) {
            solution.addItem(new Spice(item.getPricePerKilo(), remaining));
          }
        }
      }
    }
    return solution;
  }
}

Cette méthode comporte les étapes :

  • Lecture de la première ligne : poids max et nombre de pierres précieuses
  • Lecture des autres lignes : pierres précieuses et épices
  • Tri de la liste des éléments par poids au kilo décroissant
  • Ajout des éléments dans la lampe à huile
  • Écriture de la solution

Vérification (de la porte opposée)

On peut maintenant essayer les jeux de données fournis.
Avec les deux premier jeux de données cela fonctionne très bien.
Par exemple avec en entrée :

10 10 100  
485 84  
675 62  
261 35  
255 2  
817 83  
420 87  
844 64  
233 92  
403 44  
601 36  
64 60  
79 98  
92 38  
60 17  
100 70  
24 37  
3 11  
93 83  
59 36  
49 12

On obtient :

Max weight=100
Solution{items=[Jewel{pricePerKilo=127.5, weight=2}, Spice{pricePerKilo=100.0, weight=70}, Spice{pricePerKilo=93.0, weight=28}], price=9859, weight=100}
9859

Les choses se compliquent lorsque l’on essaie le troisième jeu de données :

3 10 2  
97 2  
555 1  
834 2  
25 1  
9 1  
47 2  
86 1  
14 1  
1 1  
1 1  
98 1  
36 2  
39 1

En effet on devrait obtenir une valeure de 834 mais on obtient :

Max weight=2
Solution{items=[Jewel{pricePerKilo=555.0, weight=1}, Spice{pricePerKilo=98.0, weight=1}], price=653, weight=2}
653

Si l’on regarde l’ensemble des éléments disponibles on a :

[Jewel{pricePerKilo=555.0, weight=1}, 
 Jewel{pricePerKilo=417.0, weight=2}, 
 Spice{pricePerKilo=98.0, weight=1}, 
 Spice{pricePerKilo=86.0, weight=1}, 
 Jewel{pricePerKilo=48.5, weight=2}, 
 Spice{pricePerKilo=47.0, weight=2}, 
 Spice{pricePerKilo=39.0, weight=1}, 
 Spice{pricePerKilo=36.0, weight=2}, 
 Spice{pricePerKilo=25.0, weight=1}, 
 Spice{pricePerKilo=14.0, weight=1}, 
 Spice{pricePerKilo=9.0, weight=1}, 
 Spice{pricePerKilo=1.0, weight=1}, 
 Spice{pricePerKilo=1.0, weight=1}]

Notre algorithme choisit d’abord la pierre précieuse de valeur 555, puis il ne peut pas mettre la pierre précieuse de 2 kilos car il ne reste qu’un seul kilo de libre et choisit ensuite l’épice qui vaut 98.
La solution optimale serait d’ignorer la première pierre et ensuite de choisir la deuxième pierre de 2 kilos.

PowerSet in action!

Et c’est maintenant qu’intervient le concept de PowerSet ! Qu’est-ce donc ? Il s’agit tout simplement de l’ensemble des sous-ensembles d’un ensemble. Dit comme ça c’est pas évident alors prenons un exemple. Si je reprends les trois premiers éléments du jeux de données 3 on a cet ensemble :

[Jewel{pricePerKilo=555.0, weight=1}, 
 Jewel{pricePerKilo=417.0, weight=2}, 
 Spice{pricePerKilo=98.0, weight=1}]

Tous les sous-ensembles possibles seront :

[] //Vide
[Jewel{pricePerKilo=555.0}]
[Jewel{pricePerKilo=417.0}]
[Jewel{Spice{pricePerKilo=98.0}]
[Jewel{pricePerKilo=555.0}, Spice{pricePerKilo=98.0}]
[Jewel{pricePerKilo=417.0}, Spice{pricePerKilo=98.0}]
[Jewel{pricePerKilo=555.0}, Jewel{pricePerKilo=417.0}]
[Jewel, Jewel, Spice] // L'ensemble de départ

Ce qui nous donne 8 sous-ensembles. Si l’on compte de 0 à 7 en binaire on obtient :

000   
001  
010  
011  
100  
101  
110  
111

Et c’est exactement ce sur quoi on va se baser pour générer ce PowerSet :

private static Set<List<Item>> generateAllSubLists(List<Item> items) {
  Set<List<Item>> subLists = new HashSet<>();
  int allBitMasks = (int) Math.pow(2, items.size()); 
  for (long i = 1; i < allBitMasks; i++) {
    List<Item> sublist = new ArrayList<>();
    for (int j = 0; j < items.size(); j++) {
      if ((i & (1 << j)) > 0) {
        sublist.add(items.get(j));
      }
    }
    subLists.add(sublist);
  }
  return subLists;
}

Et j’en fait quoi de ce PowerSet ?

L’astuce va être maintenant de calculer la solution optimale pour chacun de ses sous-ensembles.

Concrètement ça se passe comme cela :

// Generate all possible sub-lists (PowerSet algorithm)
Set<List<Item>> subLists = generateAllSubLists(items);
// Find best solution for each sub-set
SortedSet<Solution> solutions = new TreeSet<>();
for (List<Item> sublist : subLists) {
  Solution solution = findBestSolution(maxWeight, sublist);
  solutions.add(solution);
}
// No need to sort solutions, TreeSet implements SortedSet
Solution best = solutions.first();
System.err.println(best);
System.out.println(best.getPrice());

Notez au passage l’utilisation d’un SortedSet pour stocker la solution de chaque sous-ensemble. Les avantages vont être de garantir l’unicité des éléments et d’avoir un ensemble trié. Au niveau des désavantages on a principalement un temps d’insertion plus long. En effet l’implémentation se base sur un arbre rouge et noir (Arbre Bicolore).

On obtient maintenant le résultat escompté lorsque l’on essaie le troisième jeu de données :

Max weight=2
Solution{items=[Jewel{pricePerKilo=417.0, weight=2}], price=834, weight=2}
834

“J’tai cassé”

Malheureusement cette solution va nous poser des soucis avec le quatrième jeu de test qui contient pas moins de 200 éléments. On va se retrouver soit en OutOfMemory, soit avec un temps d’exécution qui va tendre vers l’infini (et l’au delà).
La raison tient au fait que le nombre de sous-ensembles possibles est maintenant de 2 puissance 200, soit 1.6069380442589903E60. C’est beaucoup et c’est même beaucoup trop. Parmis ces sous-ensembles se trouvent de plus des sous-ensembles avec uniquement des éléments ayant un prix au kilo bas. Il est donc fort probable que la solution obtenue pour ces sous-ensembles ne soit pas la meilleure. On va donc limiter le nombre de sous-ensembles générés :

private static Set<List<Item>> generateAllSubLists(List<Item> items) {
  Set<List<Item>> subLists = new HashSet<>();
  int allBitMasks = (int) Math.pow(2, Math.min(items.size(), 12)); 
  for (long i = 1; i < allBitMasks; i++) {
    List<Item> sublist = new ArrayList<>();
    for (int j = 0; j < items.size(); j++) {
      if ((i & (1 << j)) > 0) {
        sublist.add(items.get(j));
      }
    }
    subLists.add(sublist);
  }
  return subLists;
}

Ici on a limité à 4096 sous-ensembles, il est possible d’ajuster cette valeur en fonction du temps d’exécution souhaité, de la consommation CPU et de l’occupation mémoire.

Dans la vrai vie on peut utiliser Guava

Dans le cadre d’une compétition de code en ligne il n’est pas possible de recourir à des bibliothèques telles Apache Commons et Guava. On est donc obligé de réécrire des algorithmes, parfois de façon moins optimisé.

Dans la vrai vie j’utiliserais plutôt Guava pour générer mon PowerSet :

Set<Item> items = new Set<>();
Set<Set<Item>> powerset = Sets.powerSet(items);

D’une part c’est plus concis, d’autre part Guava a optimisé l’implémentation afin de limiter l’occupation mémoire. En effet tant que l’on n’itère pas sur les sous-ensembles l’occupation mémoire est de O(n) (n étant le nombre d’éléments de l’ensemble de départ). Je vous invite à consulter la javadoc pour plus de détails :

Performance notes: while the power set of a set with size n is of size 2^n, its memory usage is only O(n). When the power set is constructed, the input set is merely copied. Only as the power set is iterated are the individual subsets created, and these subsets themselves occupy only a small constant amount of memory.

J’espère que cet article vous a été utile !
N’hésitez pas à me faire part de vos commentaires ou questions en bas de cet article ou en m’envoyant un message sur LinkedIn :
http://www.linkedin.com/in/jbleduigou/en.
Photo de couverture par Paolo Bendandi.
Cet article a initialement été publié sur Medium.