Разбор задачи I. Переправа

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

В большинство соревнований есть задача на использование метода динамического программирования. На сайте есть большой набор задач на эту тему.

Сначала определим необходимые структуры данных:

var n,m, { количество типов лодок и грузов }
    i,j, { вспомогательные переменные }
    k, { количество погруженных в лодку грузов }
    sumw:longint; { вес грузов, помещенных в очередную лодку }
    dt:array[0..100000] of record dif,tip,prd,kol:longint; end; 
       { таблица для динамического программирования: минимальный недогруз, 
         тип использованной лодки, начиная с какого груза в очереди, 
         количество лодок }
    w:array[1..100000] of integer; { вес грузов в очереди }
    g:array[1..50] of integer; { грузоподъемность лодок }

В первой части программы выполняется ввод и инициализация массивов:

  read(n,m);
  for i:=1 to n do
    read(g[i]);
  for i:=1 to m do
    read(w[i]);
  for i:=1 to m do
    dt[i].dif:=1000000000; { бесконечность }
  dt[0].dif:=0; { для 0 грузов недогруз равен 0 }
  dt[0].kol:=0;

Далее основной цикл по заполнению таблицы. Если известен минимальный недогруз для `i-1` груза, то, перебрав все типы лодок, можно получить минимальный недогруз для следующей партии грузов.

  for i:=1 to m do
  begin
    k:=0;
    sumw:=0;
    for j:=1 to n do
    begin
      while (i+k<=m) { есть грузы в очереди }
        and (sumw+w[i+k]<=g[j]) do { и их суммарный вес не превышает 
                                   грузоподъемности лодки j-го типа }
      begin
        sumw:=sumw+w[i+k];
        inc(k);
      end;
      { в лодку j-го типа загрузили k-1 груз, начиная с i-го, весом sumw }
      { последний загруженный в лодку груз имеет номер i+k-1 }
      { недогруз составляет g[j]-sumw }
      { минимальный недогруз для предыдущего груза в dt[i-1].dif }
      if dt[i-1].dif+g[j]-sumw<dt[i+k-1].dif then { если результат улучшился }
      begin
        dt[i+k-1].dif:=dt[i-1].dif+g[j]-sumw; { запоминаем }
        dt[i+k-1].tip:=j;
        dt[i+k-1].prd:=i-1;
        dt[i+k-1].kol:=dt[i-1].kol+1;
      end;
    end;
  end;

И наконец выводим результат.

  writeln(dt[m].kol,' ',dt[m].dif);
  print(m);
  writeln;

Для вывода списка типов лодок в обратном порядке здесь используется рекурсивная подпрограмма:

procedure print(i:integer);
begin
  if i=0 then exit;
  print(dt[i].prd); { сначала выводим предыдущие значения }
  write(' ',dt[i].tip); { затем тип последней использованной лодки }
end;