Модуль: Жадные алгоритмы


Задача

1 /9


Формаджо покупает панцеротти

Теория Нажмите, чтобы прочитать/скрыть

Жадный алгоритм - это алгоритм, который на каждом шаге выбирает оптимальный (в рамках текущего шага) вариант в рассчете на то, что конечное решение окажется оптимальным в глобальном смысле.

Небольшой пример:
Пусть у нас есть неограниченное количество монет разных номиналов и нам необходимо набрать сумму S. Рассмотрим два конкретных случая, каждый из которых попробуем решить жадным алгоритмом.
А именно будем действовать так: на каждом шаге будем брать монету, наибольшего номинала (оптимальный вариант внутри шага), который не превышает оставшуюся сумму.

a) Пусть номиналы монет равны 1, 5 и 10, а S = 27.
1) Берем 10, S: 27 -> 17
2) Берем 10, S: 17 -> 7
3) Берем 5, S: 7 -> 2
4) Берем 1, S: 2 -> 1
5) Берем 1, S: 1 -> 0
В итоге набрали сумму пятью монетами. Вы можете самостоятельно (например, перебором) убедиться в том, что за 4 монеты или меньше набрать 27 не получится.

б) Пусть номиналы монет равны 1, 5 и 7, а S = 24.
1) Берем 7, S: 24 -> 17
2) Берем 7, S: 17 -> 10
3) Берем 7, S: 10 -> 3
4) Берем 1, S: 3 -> 2
5) Берем 1, S: 2 -> 1
6) Берем 1, S: 1 -> 0.
Набрали сумму шестью монетами, но могли набрать S четырьмя монетами - две номиналом 7 и две номиналом 5.

Как видно из примера, не всегда задачи можно решить жадным алгоритмом. Но если он приводит к оптимальному ответу в целом, то обычно этот способ будет проще, чем использовать динамическое программирование или другие методы.

Задача

Формаджо очень любит панцеротти с различной начинкой, причем не так важно с какой именно. Однажды, пребывая в голодном состоянии, Формаджо зашел в булочную и увидел, что в продаже присутствуют панцеротти с томатами, шпинатом и грибами.
Формаджо желает купить как можно больше панцеротти, но проблема в том, что количество панцеротти в продаже ограничено так же, как и количество денег у Формаджо.

Помогите Формаджо определить максимально возможное количество панцеротти, которые он может купить.

Входные данные:
Первая строка содержит числа P1, P2 и P3 – стоимость панцеротти с томатами, шпинатом и грибами соответственно.
Во второй строке определены значения N1, N2 и N3 – количество соответствующих панцеротти в продаже. 
В третьей строке записано число R – количество денег у Формаджо. 
Все числа во входных данных целые положительные, не превосходящие 10000.

Выходные данные:
Выведите одно целое число - максимальное число панцеротти, которые сможет приобрести Формаджо.

Пример:
 
Входные данные Выходные данные
5 3 8
2 6 4
23
7