Это проблема, которую я сделал для себя, но у меня возникают проблемы с поиском точного алгоритма без перебора для:
Уэйн собирает воду, чтобы заработать себе на жизнь. Он хочет набрать максимальное количество воды, которое он может собрать за N недель. Каждую неделю он может запускать краны максимум 39 часов. Каждый из его кранов M имеет разную скорость потока и сломается через разное время (Уэйн знает это заранее; он уже покупал такие краны раньше). Tap T имеет скорость RT галлонов / час и срок службы LT часов. Напишите программу, которая при вводе данных вычисляет максимальное количество воды, которое Уэйн может собрать за N недель. Все входные числа являются целыми числами.
Формат ввода:
N
R1 L1
R2 L2
.....
RM LM
Формат вывода:
An integer representing the maximum amount of water, in gallons, that Wayne can collect over N weeks (39*N hours, given the constraints above).
Пример ввода:
1
56 18
43 31
51 17
37 8
33 27
Пример вывода :
1875
Пояснение:
56*18+51*17=1875
Изначально я думал об использовании жадного алгоритма, в котором у вас есть переменная, которая представляет общее количество воды, собираемой Уэйном. В то время как количество оставшихся часов положительно и пока в списке кранов остались краны, вы берете кран с наибольшей общей производительностью (расход * срок службы), добавляете этот вывод к переменной, представляющей общее количество воды, вычитаете срок службы от текущего количества времени, которое осталось у Уэйна, и удалите этот кран из списка. В конце концов, если количество оставшихся часов становится отрицательным, вы вычитаете последнее добавленное количество из общего количества воды.
Однако, как вы можете видеть, это на самом деле не работает для примера I дал выше. Есть предположения? Спасибо!