На лифте за зарплатой

[к списку задач]

Задачка написана на основе лекции Михаила Геннадьевича Медведева "Жадные алгоритмы"

Ох уж эти офисные здания, понастроили по сто этажей! Офис №13 находится на сотом этаже, а бухгалтерия на первом. Перед Новым годом, в последний рабочий день перед праздниками, зарплату решили выдать наличными. Работники офиса №13 узнали об этом только за 15 минут до окончания рабочего дня, поэтому шанс получить зарплату сегодня, есть только у тех, кто немедленно сядет в лифт и спустится на первый этаж. Все работники офиса, в количестве 10 человек, бросились к лифту, около которого образовалась очередь. К сожалению, грузоподъемность лифта ограничена и составляет x килограммов, поэтому вряд в него смогут поместиться все желающие. К счастью, известен вес каждого человека стоящего в очереди, так что есть возможность отправить за зарплатой как можно большее число людей.

Требуется найти максимальное число людей, которое может уехать на лифте за один раз.

 Входные данные

В первой строке входного файла INPUT.TXT записано одно натуральное число x не превышающее 30000 - грузоподъемность лифта в килограммах.

Во второй строке записано 10 натуральных (каждое не более 150) чисел через пробел. Каждое число указывает вес человека стоящего в очереди около лифта.

Выходные данные

В файл OUTPUT.TXT выведите одно число - максимальное число людей, которое может уехать на лифте за один раз.

Пример

Немного теории от Михаила Медведева.

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

Принципиальное преимущество жадных алгоритмов состоит в простоте их понимания и реализации. В их основе лежит принцип нахождения на каждом шаге оптимального решения.

Решение.

Элементарной подзадачей является помещение в лифт одного человека. Если имеется несколько кандидатов на помещение в лифт, то оптимальным выбором будет человек с наименьшим весом, так как при этом остается наибольший запас по грузоподъемности. Для решения задачи следует отсортировать веса людей по возрастанию и помещать их в лифт, начиная с самого легкого, до тех пор, пока это возможно сделать.

Вот вариант реализации на Pascal ABC (не оптимальный вариант, т.к. последний цикл повториться n раз в любом случае, даже если переменная х станет меньше нуля уже на первом шаге):

const
  n = 10;
var
  i,j,x,y,buf,res: integer;
  a: array[1..n] of integer;
  input, output: text;
begin
  res:=0;
  Assign(input,'input.txt');
  Reset(input);
  Assign(output,'output.txt');
  Rewrite(output);
  Readln(input, x);
  for i:=1 to n do {Заполняем массив значениями из фала}
    begin
      Read(input, y);
      a[i]:= y;
    end;
  for i:=1 to n - 1 do {Сортируем массив по возрастанию методом "Пузырька"}
    for j:= i + 1 to n do
      if a[i] > a[j] then
        begin
          buf:=a[i];
          a[i]:=a[j];
          a[j]:=buf;
        end;
  for i:=1 to n do {Заполняем лифт людьми вычитая из его грузоподъемности вес пассажиров}
    if x - a[i] >= 0 then
      begin
        inc(res);
        x:=x-a[i];
      end;
  Write(output,res);
  Close(input);
  Close(output);
end.

Как было сказано выше, вариант не оптимален, но, поскольку количество итераций всего 10, то решение вполне приемлемое. Можно запустить цикл через while   и предусмотреть досрочное его завершение в том случае, если лифт уже заполнен людьми "под завязку".

[к списку задач]