Решение

Тема: динамическое программирование
Сложность: средняя

Решить эту задачу можно несколькими способами. Первый способ – динамическое программирование. Храним в таблице kol минимальное число слагаемых для получения числа `i`, а таблице how – какое слагаемое было использовано для получения числа `i` оптимальным образом. Первоначально все элементы массива kol содержат какое-то большое число, например, 1000. Массив gnome содержит гномьи слагаемые.

var gnome:array[1..54] of integer;
    kol,how:array[0..1000000] of integer;
...
for i:=0 to 1000000 do
  kol[i]:=1000;

Тогда заполнить массивы kol и how можно следующим образом:

kol[0]:=0;
for i:=0 to 1000000 do
  for j:=1 to 54 do
  begin
    k:=gnome[j]+i;
    if k<=1000000 then
      if kol[i]+1<kol[k] then
      begin
        kol[k]:=kol[i]+1;
        how[k]:=gnome[j];
      end;
  end;

Второй способ – использование запоминающей функции. Чтобы определить, сколько слагаемых потребуется для представления числа `i`, нужно найти вариант с минимальным числом слагаемых после вычитания из `i` одного из гномьих слагаемых. Чтобы повторно не решать одну и ту же задачу, результат расчета запоминаем в массивах kol и how. Вычисление функции, определяющей минимальное число слагаемых, выполняется только в том случае, если оно ранее для числа `i` не выполнялось.

function minkol(i:integer):integer;
var j,k:integer;
begin
  if kol[i]=1000 then
  begin
    if i=0 then
      kol[i]:=0
    else
    begin
      for j:=54 downto 1 do
        if gnome[j]<=i then
        begin
          k:=minkol(i-gnome[j]);
          if k+1<kol[i] then
          begin
            how[i]:=gnome[j];
            kol[i]:=k+1;
          end;
        end;
    end;
  end;
  minkol:=kol[i];
end;

Третий способ – поиск в ширину. В массиве q хранится очередь из чисел, которые нужно обработать. Первый элемент очереди извлекается и все новые числа, которые можно достичь из него прибавлением некоторого слагаемого, отмечаются в массиве kol значением на 1 больше. Достигнутые ранее числа не рассматриваются, а новые числа заносятся в очередь.

var q:array[0..1000000] of integer;
  q1,q2:integer;
...
q1:=0;
q2:=1;
q[0]:=0;
kol[0]:=0;
while q1<q2 do
begin
  i:=q[q1];
  inc(q1);
  for j:=1 to 54 do
  begin
    k:=gnome[j]+i;
    if (k<=1000000) and (kol[k]=1000) then
    begin
      kol[k]:=kol[i]+1;
      how[k]:=gnome[j];
      q[q2]:=k;
      inc(q2);
    end;
  end;
end;

Сумма выводится с использованием массива how, который заполняется во всех трех способах:

write(n,'=');
while n>0 do
begin
  write(how[n]);
  n:=n-how[n];
  if n>0 then write('+');
end;
writeln;