fork(1) download 
  1. // Из камней весом P с индексом i (i=1..N) требуется набрать кучу весом ровно W.
  2. // Если это невозможно, набрать максимально близкую к W (но меньшую, чем W).
  3. // Полный перебор при N <= 30.
  4. // Copyleft Alexey Kuzminov (c) 2016
  5.  
  6. program Stones;
  7.  
  8. const
  9.   MAX_N = 30;
  10. type
  11.   TIndex = 0..MAX_N-1;
  12.   TStones = array [TIndex] of Integer;
  13.  
  14. var
  15.   N: Integer;			
  16.   P: TStones;
  17.   i: TIndex;
  18.   W, T, tOld: LongInt;
  19.   V: LongInt;
  20.  
  21.  
  22. procedure PrintSolution(const s: String);
  23. var
  24.   k: TIndex;
  25. begin
  26.   Write(s);
  27.   WriteLn;
  28.   // текущий вес
  29.   Write(T:4,': ');
  30.   for k := 0 to N-1 do
  31.     if V shr k and 1 > 0 then
  32.       Write(P[k]:3, ' ');
  33. end;
  34.  
  35. begin
  36.   // загрузка данных и вывод задачи на консоль
  37.   ReadLn(W);
  38.   ReadLn(N);
  39.   if N > MAX_N then Exit;
  40.   Write('Набрать сумму ', W:4, ' из чисел ');
  41.   for i := 0 to N-1 do begin
  42.     Read(P[i]);
  43.     Write(P[i]:3, ' ');
  44.   end;
  45.   WriteLn;
  46.  
  47.   tOld:=0;
  48.   for V := 0 to (1 shl N)-1 do begin
  49.     // определение веса набора
  50.     T := 0;
  51.     for i := 0 to N-1 do
  52.       if V shr i and 1 > 0 then
  53.         Inc(T, P[i]);
  54.  
  55.     // все решения - было для отладки
  56.     //PrintSolution('');
  57.  
  58.     // вывод только нужных 
  59.     if T = W then begin
  60.     	if T > tOld then begin
  61.     	  // нашли первое решение
  62.     	  PrintSolution('- мусор'#13'Решения:');
  63.     	  tOld := T;
  64.     	end
  65.     	else
  66. 		  PrintSolution('');
  67.     end
  68.     else if T < W then begin
  69.       // может быть решением, если набрать не удастся
  70.       if T > tOld then begin
  71.    	    PrintSolution('- мусор');
  72.         tOld := T;
  73.       end
  74.       else if T = tOld then
  75.         PrintSolution('');
  76.       // случай T < tOld не выводим
  77.     end;
  78.   end;
  79. end.
Success #stdin #stdout 0s 280KB
comments (?)
stdin 
9
4
2 8 2 4
stdout 
Набрать сумму    9 из чисел   2   8   2   4 

   0: - мусор
   2:   2 - мусор
   8:   8 
   8:   2   2   4
https://ideone.com/g70YJK
Набор суммы из данных чисел
language:
Pascal (fpc 3.0.4)
created:
9 years ago
visibility:
secret

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!