  J.57. Se dau N cupoane de materiale de lungimi L1, L2, ..., Ln si preturi
unitare P1, P2,..., Pn. Sa se determine o multime de cupoane de valoare totala
maxima, astfel incat lungimea totala a cupoanelor care intra in multime sa nu
depaseasca o valoare data Lmax. In plus se considera ca nu orice doua cupoane
pot fi selectate impreuna. Ca date de intrare se dau numarul de cupoane,
lungimea maxima si pentru fiecare cupon lungimea si pretul unitar precum si o
lista de perechi de cupoane incompatibile. Se vor afisa indicii corespunzatori
cupoanelor selectate in multime precum si lungimea si valoarea totala a
cupoanelor.
==================================  (Zalau 1995)
Solutie (Mihai Stroe)

    Aceasta este o problema specifica pentru metoda backtracking.
    Pecizarea ca exista cupoane incompatibile inlatura orice sansa de a
  folosi programarea dinamica.
    Se genereaza submultimi ; un element poate intra intr-o submultime
  daca este compatibil cu toate cupoanele deja selectate.Elementele se
  genereaza in ordine crescatoare.Se verifica la introducerea unui element
  daca lungimea totala nu depaseste lungimea Lmax.Fiecare submultime valida
  este comparata cu optimul partial, care este actualizat daca e cazul .
    Pentru a optimiza cautarea se testeaza euristic la fiecare pas daca
  exista sanse sa se ajunga la o solutie mai buna,astfel:se aduna la valoarea
  generata valoarea totala a submultimii [i+1,i+2,...,n],unde i este numarul
  ultimului cupon introdus.Daca rezultatul e mai mic decat optimul,nu se poate
  ajunge la solutie.Daca nu s-a oprit cautarea,se aplica o a doua euristica,
  mai puternica: se aduna la valoarea actuala suma valorilor tuturor
  cupoanelor compatibile cu cupoanele din submultime si se compara cu optimul
  partial.A doua euristica este mai lenta,dar elimina mai multe cautari
  inutile.

}

var a:array[1..100,1..100]of byte;
    lung,pret:array[1..100]of byte;
    st,sol:array[1..100]of byte;
    lmax,suma,cost,copt,lopt,i,j,k,l,m,n:word;
    cst:array[1..100]of byte;
    f:text;
    s:string;
    luate:set of byte;

function valid:boolean;
begin
  valid:=false;
  if st[k]<=st[k-1]then exit;
  if suma+lung[st[k]]>lmax then exit;
  if cost+cst[st[k]]<copt then exit;
  for i:=1 to st[k]-1 do
      begin
        if (i in luate)and(a[i,st[k]]=1)then exit;
      end;
  l:=0;
  for i:=st[k]+1 to n do
      begin
        m:=0;
        for j:=1 to k-1 do
            if a[i,st[j]]=1 then m:=1;
        if m=0 then inc(l,pret[i]);
      end;
  if l+cost<copt then exit;
  valid:=true;
end;

procedure react;
begin
  if cost>copt then begin copt:=cost;sol:=st;lopt:=suma;end;
end;

procedure tipar;
begin
  for i:=1 to n do if sol[i]<>0 then write(sol[i],' ');
  writeln;
  writeln('lungime=',lopt,'  valoare=',copt);
  readln;
end;

begin
  writeln('Introduceti numele fisierului de intrare ');
  readln(s);
  assign(f,s);
  reset(f);
  readln(f,n,lmax);
  for i:=1 to n do
      begin
        read(f,lung[i]);
        read(f,pret[i]);
        pret[i]:=pret[i]*lung[i];
        while not seekeoln(f) do
          begin
            read(f,j);
            a[i,j]:=1;
            a[j,i]:=1;
          end;
        readln(f);
      end;
  for i:=n downto 1 do
      cst[i]:=cst[i+1]+pret[i];
  k:=1;
  while k>0 do
    begin
      repeat inc(st[k]);until(st[k]>n)or((st[k]<=n)and valid);
      if st[k]>n then
         begin
           st[k]:=0;
           dec(k);
           luate:=luate-[st[k]];
           suma:=suma-lung[st[k]];
           cost:=cost-pret[st[k]];
         end
         else
         begin
           luate:=luate+[st[k]];
           suma:=suma+lung[st[k]];
           cost:=cost+pret[st[k]];
           react;
           inc(k);
         end;
    end;
  tipar;
end.
