fork download
copy 
  1. program menu;
  2. Uses math;
  3. const
  4.      MAX=5005;
  5. var
  6.     N,B,i,j,massimo : integer;
  7.     Prezzo:array[1..MAX] of integer;
  8.     tab:array[0..MAX,0..MAX] of integer;
  9.     preso:array[1..MAX] of boolean;
  10.     uscita:boolean;
  11. begin
  12. 	readln(N,B);
  13. 	for i:=1 to N do readln(Prezzo[i]);
  14. 	for i:=0 to N do 
  15. 	          for j:=0 to B do tab[i,j]:=0;
  16. 	for i:=1 to N do preso[i]:=false;          
  17. 	for i:=1 to N do
  18. 	            begin
  19. 	              for j:=1 to B do 
  20. 	                             if j<Prezzo[i] then tab[i,j]:=tab[i-1,j]
  21. 	                                            else 
  22. 	                                                  if tab[i-1,j]>tab[i-1,j-Prezzo[i]]+ Prezzo[i] then tab[i,j]:=tab[i-1,j] 
  23. 	                                                                                                else tab[i,j]:=tab[i-1,j-Prezzo[i]] + Prezzo[i];
  24.               end;                   
  25.     i:=N;  massimo:=tab[N,B]; j:=massimo;
  26.     while (i>0) and (j>0) do 
  27.                             if tab[i,j]<>tab[i-1,j] then begin preso[i]:=true;j:=j-Prezzo[i];i:=i-1;  end
  28.                                                     else i:=i-1;
  29.    for i:=1 to B  do if preso[i]=true then writeln (Prezzo[i]);  
  30.  end.
Success #stdin #stdout 0s 5304KB
comments (?)
stdin
copy 
4 100
60
40
30
20
stdout
copy 
60
40
https://ideone.com/ymPqSE
language:
Pascal (fpc 3.0.4)
created:
12 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!