Простая задача по программированию. На лифте за зарплатой
 
Информатика в школе


Видео курсы для чайников фотошоп, joomla, wordpress, php, css 
  Главная  ●  Карта сайта
 
 

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

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

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

 

 

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

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

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

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

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

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

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

Пример

INPUT.TXT OUTPUT.TXT
300
100 50 100 50 100 50 100 50 100 50
5

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

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

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

Решение.

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

Вот вариант реализации на 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   и предусмотреть досрочное его завершение в том случае, если лифт уже заполнен людьми "под завязку".

 

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

 

Книжные новинки
Как сделать свой сайт и заработать на нем Е. Мухутдинов
Копилка
Рабочие программы
Проекты MS Office
Презентации
Открытые уроки
Экзаменационные билеты
Элективные курсы
Бесплатный soft
 Инструкции по ТБ
Подготовка к олимпиадам по информатике
Методика подготовки
"Золотые" алгоритмы
Простые задачи для начинающих
Олимпиадные задачи с решениями
Книги
Среда программирования
Обучение программированию на С++
Справочник по языку Pascal
Обучение
Подготовка к ЕГЭ
Создание сайтов
Уроки FrontPage
Уроки Word 2003
Создание игр на Delphi
Печатаем вслепую

Информация

Наши интервью
Книга почета
Курсы повышения квалификации
Электронная библиотечка
Книжная полка
Статьи
Полезные ссылки
Обратная связь

Конкурсы

Олимпиада
Фотоконкурс
VIP
Персональный раздел профессора
Макаровой Н.В.
Персональный раздел профессора
Смыковской Т.К.