KNAPSACK
KNAPSACK
  PL_FILE KNAPSACK
    DOC
      le pb du bin_packing consiste à mettre une maximum d'objets de taille différente dans un sac de taille finie.
      le probleme du Knapsack consiste à maximiser une fonction de valeur, tout enmettant les objets dans une boite de taille finie
      parametres
        taille de la boite
          taille_max
        liste des tailles des objets
          liste_objets
    notation
      ' >= ' ::= ' => '
      ' <= ' ::= ' =< '
    DONNEES DE BASE
      liste_objets ([1, 3, 5, 6, 7, 9, 11])
        DEF_DB objets, taille, valeur
          taille
            1
              5
                valeur
            3
              15
                valeur
            5
              9
                valeur
            6
              5
                valeur
            7
              2
                valeur
            9
              2
                valeur
            11
              7
                valeur
      taille_max (30)
    resoud (S, N) :-
      taille_max (T)
        liste_objets(L)
          c'est parti
      nb_setval (best, 0)
        nb_setval (best_sol, [])
      solve_bp (L, T, 0, S, N)
      affiche juste les meilleures
        nb_getval (best, B)
          IF B < N
            nb_setval (best_sol, S)
              nb_setval (best, N)
                echo (solution (N, S))
              montre_sol
            fail
    resoud_ks (S, N, V) :-
      taille_max (T)
        liste_objets(L)
          c'est parti
      nb_setval (best, 0)
        nb_setval (best_sol, [])
      solve_ks (L, T, 0, 0, S, N, V)
      affiche juste les meilleures
        nb_getval (best, B)
          IF B < V
            nb_setval (best_sol, S)
              nb_setval (best, V)
                echo (solution (N, S))
              montre_sol
            fail
    montre_sol :-
      nb_getval (best_sol, S)
        nb_getval (best, N)
          echo (solution (N, S))
    DEF_IO solve_bp
      in
        L, T, K
          S, N
            out
          echo solve (L, T, K, S, N)
            goals
            fail
        [], T, K
          [], K
            out
          terminal
            goals
        X .. L, T, K
          X .. S , N
            out
          echo solve (L, T, K, S, N)
            goals
          normal
            goals
          K1 is K + X
            goals
            K1 <= T
              echo (X . L, T, K, K1)
              solve_bp (L, T, K1, S, N)
        X .. L, T, K
          sans l'objet
            goals
            solve_bp (L, T, K, S, N)
          S , N
            out
    DEF_IO solve_ks
      in
        L, T, K, V
          S, N, V2
            out
          echo solve (L, T, K, V, S, N, v2)
            goals
            fail
        [], T, K, V
          [], K, V
            out
          terminal
            goals
        X .. L, T, K, V
          X .. S , N, V2
            out
          K1 is K + X
            goals
            K1 <= T
              echo (X . L, T, K, K1)
              objets (X, Y)
                V1 is V + Y
              solve_ks (L, T, K1, V1, S, N, V2)
        X .. L, T, K, V
          sans l'objet
            goals
            solve_ks (L, T, K, V, S, N, V1)
          S , N, V1
            out
    DEF member_next , L, X, Reste
      args
        X .. L, U, V
          OR
            goals
            U = X
              L = V
            member_next (L, U, V)
    DEF_IO member_tuples, L, N, Tuple
      in
        [], 0
          []
            out
          Sous-sujet 2
            goals
        L, 0
          []
            out
          !
            goals
        L, K
          demande plus d'éléments que possible
            notes
          _
            out
          length (L, Long)
            goals
            Long > K
              !
                fail
        L, K
          X .. U
            out
          member_next (L, X, L1)
            goals
            K1 is K -1
              member_tuples (L1, K1, U)
    some tests
      t1 (X) :-
        member_tuples ([1, 2, 3, 4], 2, X)
      t2 (X):-
        member_tuples ([1, 2, 3, 4], 3, X)
      t3 (X):-
        member_tuples ([1, 2, 3, 4], 4, X)
  ici