Подсчет количества автомобилей для перевозки n пассажиров?

Question

[amorphine]

Имеется несколько автомобилей вместимостью: например, 3, 4, 7 и 30.
У каждого вида автомобиля имеется коэффициент, влияющий на стоимость поездки. Например:

{
     3: 1,
     4: 1.2,
     7: 1.6,
     30: 4.2,
}

Подскажите, пожалуйста, алгоритм, чтобы подсчитать, сколько потребуется автомобилей и какой вместимости для n количества человек при условии, что конечный коэффициент стоимости поездки должен быть минимальным?

Comments

[Иван Филатов]

Смотря какие требования по количеству машин и т.п.

[amorphine]

Иван Филатов, дополнил вопрос, введя коэффициент стоимости поездки на каждый автомобиль. Требования - минимальный итоговый коэффициент стоимости поездки.

Answer 1

[Rsa97]

Если нет других ограничений, то [(n-1)/30]+1 30-местных автомобилей.

Comments

[amorphine]

Спасибо, исправил формулировку задачи.

[Rsa97]

amorphine, Теперь остаётся понять, что и с каким приоритетом рассматривать. Скажем, что лучше на 14 человек - 2 автомобиля по 7 мест (2 авто, но 0 пустых мест) или 1 автомобиль на 30 мест (1 авто, но 16 пустых мест)?

[amorphine]

Rsa97 снова дополнил условия. Общий коэффициент стоимости поездки должен быть минимальным.
У меня нет четкого ТЗ на этот счет, поэтому изначально были столь пространные условия задачи.
Возможно, ошибаюсь, но в реальной жизни можно рассчитывать на то, что если приоритет отдается заполненности ТС, то получится оптимальный вариант набора автомобилей.

[Rsa97]

amorphine,
Для начала определяем, сколько будет полных 30-местных автомобилей.

c30 := [n / 30]
остаток := n % 30

Теперь смотрим, один 30-местный стоит столько же, сколько и 4.2/1.6 = 2.625 7-местных.
Значит три-пять 7-местных выгодно заменить 30-местным.

если остаток > 14 то 
  c30 := c30+1
  остаток := 0
конец если

Заполним теперь семиместные

c7 := [остаток / 7]
остаток := остаток % 7

Смотрим, если осталось 5 или 6 человек, то выгоднее отправить ещё один семиместный, чем два меньшей вместимости.

если остаток > 4 то
  c7 := c7 + 1
  остаток := 0
конец если

Осталось от 0 до 4 человек. Логично, что четверых лучше отправить одним четырёхместным, а меньшее количество трёхместным.

если остаток = 4 то
  c4 := 1
  c3 := 0
иначе если остаток > 0 то
  с4 := 0
  c3 := 1
конец если

[amorphine]

Rsa97, спасибо, что решили помочь.
Здесь без математически доказанного алгоритма не получится.
Ход предложенного решения скорее всего подойдет к реальному миру, но если вдруг коэффициенты веса будут безумными, то уже появятся проблемы.

[Rsa97]

amorphine, А здесь и общий алгоритм будет похожим. Для каждого типа автомобиля, начиная с самого вместительного, проверяем, выгодно ли его полностью заменить автомобилями с меньшим количеством мест.
([(30-1)/7]+1)*1.6 = 8 > 4.2, невыгодно
([(30-1)/4]+1)*1.2 = 9.6 > 4.2, невыгодно
([(30-1)/3]+1)*1 = 10 > 4.2, невыгодно
([(7-1)/4]+1)*1.2 = 2.4 > 1.6, невыгодно
([(7-1)/3]+1)*1 = 3 > 1.6, невыгодно
([(4-1)/3]+1)*1 = 2 > 1.2, невыгодно

Если есть пары, где условие не выполняется, выбрасываем из анализа автомобили.
Затем, начиная с автомобиля с максимальным количеством мест, проводим следующий цикл:
Находим количество полностью заполненных автомобилей.
Находим количество пассажиров, которых выгоднее перевезти данным типом, а не несколькими предыдущими.
Если остаток пассажиров больше или равен найденному, то добавляем ещё один автомобиль текущего типа, анализ закончен.
Иначе переходим в начало цикла с остатком пассажиров.
Если цикл дощёл до конца, а пассажиры ещё остались, добавляем один автомобиль минимальной вместимости.

Пусть n = 99
c30 := [99/30] = 3
rest := 99%30 = 10
9 > [4.2/1.6]*7 ? нет, продолжаем
c7 := [9/7] = 1
rest := 9%7 = 2
2 > [1.6/1.2]*4 ? нет, продолжаем
c4 := [2/4] = 0
rest := 2%4 = 2
2 > [1.2/1]*3 ? нет, продолжаем
c3 := [2/3] = 0
rest := 2%3 = 2
2 > 0 ? да => c3 := c3+1 = 1

Answer 2

[terrier]

Это вариация на тему задачи об укладке рюкзака. Теоретически она NP-полная. Практически подходы к решению есть: самое простое, конечно отсортировать автомобили по возрастанию удельного коэффициента стоимости поездки ( на человека, то есть
4.2 / 30 = 0.14
1.6 / 7 = 0.22
1.2 / 4 = 0.3
...)
и выбирать автомобили по списку сверху вниз. Однако помним, что так мы можем получить решение, наверное, разумное, но сколько угодно далекое от оптимального.