Другие языки программирования и технологии

Напишите программу на Pascal. В цистерне N литров молока.

Напишите программу на Pascal. В цистерне N литров молока. Есть бидоны объёмом 1, 5. и 6 литров. Нужно разлить молоко в бидоны так, чтобы они все были заполнены и их количество были минимальным. С клавиатуры или из файла вводится объём цистерны, количество типов бидонов и их размеры
"Жадный" алгоритм, заполняющий сначала самые большие, а потом маленькие, НЕПРАВИЛЬНЫЙ ОТВЕТ.

Для начала, этот алгоритм может не сойтись.
Я в каком-то из ответов это демонстрировал. Программа оттуда: http://ideone.com/54MNp0
Хотя решений вообще может не быть. Например, когда N - нечетное, а размер всех бидонов - четный.

Но, главное, если даже "жадный" алгоритм сошелся, то нельзя сказать, что количество вёдер будет минимальным. Пример: нужно набрать 8 литров ведрами 5 4 1. "Жадный" выдаст 5 1 1 1, а правильный 4 4.

Пока единственный гарантированный способ - честно перебрать все варианты.
Этот способ нормально работает при маленьких количествах бидонов.

Для больших - есть идея вариации готового решения, пытаясь улучшить его (работает даже когда жадный алгоритм не сошелся)
В нашем примере:
1. есть решение 1по5 3по1 и 0 в остатке
2. выбросим 5 и заменим его следующим числом 4 (на самом деле нужно брать 5div4 числа 4)
получим 1по4 3по1 и недостаток 1
3. суммируем всё ПОСЛЕ 4 и пытаемся найти оптимальное решение для 4 литров молока.

Исходно было 8, поэтому поиск оптимума для 4 - уже прогресс.

Замечание:
Если бы 5-литровых бидонов в решении было больше, то можно было бы убрать потом 2 из них, а на следующий раз - 3. Но нужно помнить убрав от 1 до всех, мы получим тот же полный перебор.
Поэтому исходить надо из соотношения 5 и 4. В данном случае 3 5-литровых - это максимум, так как 5*3 меньше 4*4, а уже 5*4 = 4*5 - такая замена увеличивает количество ведер.
Александр Клочев
Александр Клочев
11 112
Лучший ответ
заполняй сначала самые большие, потом поменьше и остаток в литровые, примени div, mod
Александр Шевцов Если грубо, то этот алгоритм не работает в такой задаче.