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

Question

Я столкнулся с проблемой, которая заключается в следующем: на парковке есть машины, каждый водитель берет определенную сумму, чтобы припарковать свою машину, водитель будет недоволен, если время, которое он должен ждать, больше, чем времяон берет, чтобы припарковать машину, что означает, что водители, которые находятся впереди его в очереди, занимают больше времени, чтобы припарковать свои машины.Я хочу найти последовательность, которая минимизирует количество драйверов в линии.Например: 2 15 1 5 3 -> это последовательность драйверов в линии.Первый водитель, очевидно, будет счастлив, так как ему не нужно никого ждать, второй в строке (15) занимает 15 минут для парковки, но должен ждать только 2 минуты, поэтому он тоже будет счастлив, проблема начинается с третьеговодитель и тд.Я хочу переставить их так, чтобы количество недовольных водителей было минимальным.Я пришел к решению, которое находит все варианты элементов в списке и находит несчастные драйверы для каждого из них, но кажется, что оно очень медленное, когда количество драйверов увеличивается на огромную величину.Мой код:

import itertools
driverList = input().split()
for i in range(len(driverList)):
    driverList[i] = int(driverList[i])


permutationList = []
permutationList += list(itertools.permutations(driverList))

maxCount = 1
for i in range(len(permutationList)):
    count = 1
    sumCount = permutationList[i][0]
    for j in range(1, len(permutationList[i])):
        if permutationList[i][j] > sumCount:
            count += 1
        sumCount += permutationList[i][j]
    if count > maxCount:
        maxCount = count

print(maxCount)

Есть ли какой-либо другой способ или структура данных, которые я могу использовать, чтобы сделать этот алгоритм намного более эффективным.Большое спасибо.Ответом для ввода «2 15 1 5 3» будет 4, этот ответ задается причиной, если автомобили переставляются в последовательности «1 3 5 2 15», количество счастливых водителей будет 4.

• 1> 0 (счастливый)
• 3> 1 (счастливый)
• 5> 3 + 1 (счастливый)
• 2 <5 + 3 +1 (несчастный) </li>
• 15> 2 + 5 + 3 + 1 (счастливый)

Answer 1

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

#!/usr/bin/env python3

def happiest_drivers(drivers):
    drivers = sorted(drivers)
    assert drivers and drivers[0] > 0
    rv = []
    wait = 0
    # First, repeatedly find the fastest driver who will be happy.
    for i, d in enumerate(drivers):
        if d > wait: # or >= if that makes more sense
            rv.append(d)
            drivers[i] = 0
            wait += d
    num_happy = len(rv)
    # Then add all the unhappy drivers. There's nothing we can do about them.
    for d in drivers:
        if d:
            rv.append(d)
    return rv, num_happy

def main():
    order, num_happy = happiest_drivers([int(x) for x in input().split()])
    print('%d/%d happy with order %r' % (num_happy, len(order), order))

if __name__ == '__main__':
    main()

Answer 2

Использование одного для цикла:

import random

# set num drivers
NUM_DRIVERS = 5
# set max wait time
MAX_WAIT_TIME = 20

# create driver parking list - max out at 20 min parking job
parking = [random.randint(1, MAX_WAIT_TIME) for _ in range(NUM_DRIVERS)]

parking
# [20, 16, 4, 4, 2]

def happy_drivers(parking_list):
    """
    happy_drivers takes an input list and returns a custom ordered 
    list of driver wait times before they become unhappy. 

    Each item in the list contains the maximum amount of time 
    a driver is willing to wait to park a vehicle before they become
    unhappy. Additionally, this wait time also corresponds to how long it 
    takes them to park a vehicle. 

    Take an input list [20, 10, 4, 4, 2]. An optimal happy ordering 
    could be parking cars in [2, 4, 10, 20, 4] where there are 4 happy drivers. 
    If the drivers were simply sorted, i.e. [2, 4, 4, 10, 20], 
    there would only be 2 happy drivers. 

    Parameters
    -----
    parking_list - list
        Input list of maximum wait times per driver

    Returns
    -----
    new_driver_list - list
        Sorted driver list based on creating the fewest unhappy
        drivers

    happy_driver_idx - int
        Number of happy drivers who didn't have to wait longer
        than their max wait time
    """
    # sort parking
    sorted_parking = sorted(parking_list)
    cur_wait = 0
    new_driver_list = []
    happy_driver_idx = 0
    for i, item in enumerate(sorted_parking):
        if item > cur_wait:
            cur_wait += item
            new_driver_list.insert(happy_driver_idx, item)
            happy_driver_idx += 1
        else:
            new_driver_list.append(item)

    return new_driver_list, happy_driver_idx

optimal_ordering, happy_drivers = happy_drivers(parking)
print("""An optimal ordering: {}\nNum happy drivers: 
     {}""".format(optimal_ordering, happy_drivers))

# An optimal ordering: [2, 4, 16, 4, 20]
# Num happy drivers: 3

Answer 3

Просто используйте функцию list.sort (), чтобы расположить числа в порядке возрастания / убывания.Для получения дополнительной информации (list.sort ()) в записной книжке ipython