--*   LE PROBLEME DU SAC-A-DOS   *

with ENSEMBLE_DE;
generic  NB_CHARGES: positive;
package  SAC_A_DOS is
  subtype NUMERO_CHARGE is positive range 1..NB_CHARGES;
  subtype poids is positive;
  type LISTE_DE_POIDS is array (NUMERO_CHARGE) of poids;

  package p_ens is new ENSEMBLE_DE (numero_CHARGE); use p_ens;
  subtype ENS_CHARGE is ENSEMBLE;	-- renommage.
  function EST_VIDE (E: ens_CHARGE) return boolean;

  generic   with procedure traiter (p: poids);
  procedure LISTE_DES_CHARGES (E: ens_charge; ch: LISTE_DE_POIDS);

  procedure DECOMPOSER (LA_MASSE:in POIDS; EN:in LISTE_DE_POIDS;
			RESULTAT:in out ENS_CHARGE);
end sac_a_dos;

package  body SAC_A_DOS is

  function EST_VIDE (E: ens_CHARGE) return boolean is
  begin
    return E = ENS_VIDE;
  end;

  procedure LISTE_DES_CHARGES (E: ens_charge; ch: LISTE_DE_POIDS) is
    procedure trait_num (num:numero_charge);
    procedure enumerer_les_charges is new POUR_TOUS (trait_num);
    procedure trait_num (num:numero_charge) is
    begin
      TRAITER (CH (num));
    end;
  begin
    enumerer_les_charges (E);
  end;

  procedure DECOMPOSER (LA_MASSE:in POIDS; EN:in LISTE_DE_POIDS;
			RESULTAT:in out ENS_CHARGE) is
    NP: natural range 0..en'last:=0;  	-- pseudo-pile.
    residu: natural:=LA_MASSE;		-- masse residuelle.
    weight: LISTE_DE_POIDS renames EN;
  begin
    RESULTAT:= ENS_VIDE;
	    -- La pile NP definit le sort des poids numerotes 1 a NP.
    loop
      loop				 -- Phase d'empilement.
	   NP := NP + 1;
	   if weight (NP) <= residu then -- inclure le poids no. NP
	      residu:= residu - weight (NP);
	      RESULTAT:= RESULTAT + NP;
	      if residu = 0 then RETURN; end if;  -- succes obtenu.
	   end if;
	   exit when NP = weight'last;		  -- echec...
      end loop;				-- (fin empiler).
      loop				-- On depile (partiellement).
	if DANS (NP, RESULTAT) then	-- exclure le poids no. NP
	   RESULTAT:= RESULTAT - NP;
	   residu:=residu + weight (NP);
	   exit when NP < weight'last;
	end if;
	NP := NP - 1;	   		-- On depile.
	if NP = 0 then RETURN; end if;	-- echec definitif ("pile vide").
      end loop;				-- (fin depiler).
    end loop;
  end Decomposer;
end sac_a_dos;