Python-сообщество

Алгоритм который написал я работает верно. Может вы сможете его улучшить, использую некоторые особенности самого языка. Я просто python только начал изучать и не знаю этих особенностей.

Получилось такое

 from itertools import groupby
 
groups = [1, 1, 1, 1, 1, 1, 2, 2, 3, 3, 4, 4]
 
amounts = {k: len(tuple(g)) for k, g in groupby(sorted(groups))}
x4 = amounts.get(4, 0)
x3 = amounts.get(3, 0)
x2 = amounts.get(2, 0)
x1 = amounts.get(1, 0)
 
x12 = x1 - x2 % 2 * 2
if x12 < 0:
    x12 = 0
x13 = x12 - x3
if x13 < 0:
    x13 = 0
y = x4 \
    + x2 // 2 \
    + x2 % 2 \
    + x3 \
    + x13 // 4 \
    + (x13 % 4 > 0)
 
print y

Отредактировано Shaman (Дек. 26, 2016 19:08:44)

polsovatel
Может вы сможете его улучшить

Shaman, Ваш алгоритм тоже неверный. При последовательности 1 1 1 2 2 3 программа вернет 4, но на самом деле будет 3.

polsovatel
Похоже, что это NP-полная задача, то есть решается только перебором всех вариантов. Ваше решение, как я выше уже писал, если оно работает, то работает только для частного случая, что не есть гуд.

Разве если перебирать все варианты программа не будет медленно работать?

polsovatel
Тормозить - понятие относительное. Обычно в задачах перебора, степень торможения увеличивается с ростом итераций. Может увеличиваться линейно, а может квадратично, а может и экспоненциально. Зависит от алгоритма. Таких задач на самом деле много, взять хотя бы знаменитую задачу коммивояжера. Ваша - одна из таких, надо перебирать все варианты с учетом всех возможных оптимизаций. То есть вам надо придумать алгоритм так, чтобы он работал на любых целочисленных значениях констант MAX_CAR_COPACITY и MAX_GROUP_LEN и расходовал как можно меньше ресурсов. При этом (это чисто моя оценка, я могу быть не прав) вам придется решать NP-полную задачу.

polsovatel
Shaman, Ваш алгоритм тоже неверный. При последовательности 1 1 1 2 2 3 программа вернет 4, но на самом деле будет 3.

FishHook
вы захардкодили требование “четыре человека в машине”