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

Добрый вечер. Есть такая задача:
После окончания уроков n групп школьников вышли на улицу и собрались ехать домой к Поликарпу на празднование его дня рождения. Известно, что i-ая группа состоит из si друзей (1 ≤ si ≤ 4), которые не хотят расставаться по пути к Поликарпу. Решено ехать на такси. Каждая машина может вместить не более четырех пассажиров. Какое минимальное количество машин потребуется школьникам, если каждая группа должна целиком находиться в одной из машин такси (но одна машина может вмещать более чем одну группу)?

Я написал алгоритм(он вроде даже правильный), но по времени очень громоздкий. Не подскажите как можно ускорить программу. Или как хотя бы через профилировщик посмотреть где много времени съедается.
Заранее спасибо.

lst = []

def func1(lst):
    numberGroup = input()
    string = input()
    lst = list(string.replace(' ', ''))

    for i in range(0, len(lst)):
        lst[i] = int(lst[i])
    return lst

lst = func1(lst)

def func(lst):
    k = -1
    counter = 0
    for i in range(0, len(lst)):
        if lst[i] == 4:
            lst[i] = 0
            counter = counter + 1
        
        elif lst[i] == 3:
            counter =counter + 1
            lst[i] = 0
            if lst.count(1) != 0:
                lst[lst.index(1, 0, len(lst))] =  0

        elif lst[i] == 2:
            counter = counter + 1
            lst[i] = 0
            if lst.count(2) != 0:
                lst[lst.index(2, 0, len(lst))] = 0
            elif lst.count(1) > 1:
                lst[lst.index(1, 0, len(lst))] = 0
                lst[lst.index(1, 0, len(lst))] = 0
                
            elif lst.count(1) == 1:
                lst[lst.index(1, 0, len(lst))] = 0
        
    for i in range(0, len(lst)):
        if  lst[i] == 1:
            k = k + 1
    if lst.count(1) != 0:
        counter = counter + int(k * 0.25 + 1)
    return counter

counter = func(lst)
print(counter)

Отредактировано polsovatel (Дек. 24, 2016 01:15:05)

polsovatel
код на форумах нужно оформлять в теги code

Исправил

polsovatel
Чего-то вы нагородили лишнего, как мне кажется. У меня получился такой алгоритм

  
groups = [3, 2, 1, 4, 4, 3, 2,  1, 1]
car_capacity = 4
crews = []
s_groups = sorted(groups)
crew = []
for index, group in enumerate(s_groups):
    if not crew:
        crew = [group]
    if index < len(groups) - 1:
        if sum(crew) + s_groups[index + 1] <= car_capacity and len(crew) < car_capacity:
            crew.append(s_groups[index + 1])
        else:
            crews.append(crew)
            crew = []
    else:
        crews.append(crew)
print s_groups
print crews
print "RESULT=", len(crews)

Отредактировано FishHook (Дек. 24, 2016 08:58:14)

Добрый день. Ваш алгоритм работает не корректно. Например если список groups будет таким: 1, 1, 1, 1, 1, 1, 2, 2, 3, 3, 4, 4. Программа покажет 7, но на самом деле 6.
Для верного ответа надо для начала посадить все группы по 4, потом смотреть где группа по 3 и если есть группа из одного человека, то сажать его в машину вместе с группой из трех…. Ваш же алгоритм сажает сначала все группы из одного человека,потом из 2-ух…

Например если список groups будет таким: 1, 1, 1, 1, 1, 1, 2, 2, 3, 3, 4, 4. Программа покажет 7, но на самом деле 6.

polsovatel
Ваш же алгоритм сажает сначала все группы из одного человека,потом из 2-ух…

4-1-ая группа
4-2-ая группа
3+1-3-я группа
3+1-4
2+2-5
Оставшиеся единицы в 6

Это будет самый оптимальный способ для данного примера

Ok, согласен, надо подумать