@YaDelfinchik

Как решить задачу?

Прошу помочь с заданием. Написал свою функцию, но она верна только в 7 из 10 тестов, а проверить где ошибка не могу, аргументы тестов скрыты. Думаю, что есть какое-то простое решение которого я не вижу или не знаю.

Само задание:
61eaf57519475218421856.png

Мой код который работает в 7 из 10 случаев:

def get_result(weight):
    import random
    x = weight.copy()
    x_clone = x.copy()
    count = 0
    a_count = 0
    max_list = []
    temp_list = []
    back_list = []

    if len(x) % 4 == 0:
        how_car = int(len(x) / 4)
    else:
        how_car = int((len(x) // 4) + 1)
    x_clone.sort()

    for i in range(1, how_car + 1):
        max_list.append(x_clone[-1])
        x_clone.remove(max_list[-1])

    random.shuffle(x_clone)

    for i in x_clone:
        if i > 210:
            how_car += 1
            max_list.append(i)
            x_clone.remove(i)
        continue

    while len(x_clone) >= 3:
        while len(temp_list) < 3:
            temp_list.append(x_clone[0])
            x_clone.remove(x_clone[0])
        if sum(temp_list) <= 210:
            back_list.append(temp_list.copy())
            print(back_list)
            temp_list.clear()
            continue
        else:
            x_clone.extend(temp_list)
            random.shuffle(x_clone)
            temp_list.clear()
            count += 1
            if count == 10000:
                back_list.clear()
                x_clone = x.copy()
                x_clone.sort()
                max_list.clear()
                how_car += 1
                for i in range(1, how_car + 1):
                    max_list.append(x_clone[-1])
                    x_clone.remove(max_list[-1])
                count = 0
                continue
            if len(x_clone) == 3:
                x_clone.extend(back_list[0])
                back_list.remove(back_list[0])
                a_count += 1
                continue
            if a_count == 10000:
                back_list.clear()
                x_clone = x.copy()
                x_clone.sort()
                max_list.clear()
                how_car += 1
                for i in range(1, how_car + 1):
                    max_list.append(x_clone[-1])
                    x_clone.remove(max_list[-1])
                    continue
                a_count = 0
            continue

    while 3 > len(x_clone) > 1:
        if sum(x_clone) <= 210:
            x_clone.clear()
        else:
            if len(back_list) < len(max_list):
                x_clone.remove(max(x_clone))
            else:
                how_car += 1
                x_clone.remove(max(x_clone))

    while len(x_clone) == 1:
        if x_clone[0] > 210:
            how_car += 1
            x_clone.clear()
        else:
            x_clone.clear()

    if len(x_clone) == 0:
        return (how_car)

  • Вопрос задан
  • 101 просмотр
Пригласить эксперта
Ответы на вопрос 1
Vindicar
@Vindicar
Ну идея такая...
Допустим у нас K человек, и предположим что мы вызвали N машин. Первую оценку N1 можно получить так - это количество чисел больше 210. Меньше этого количества машин мы не обойдемся.
Вторую оценку N2 можно получить так: число человек / 4 и округлить вверх. Соответственно, начинаем поиск N начиная с max(N1, N2) и идём вверх.

Раз на переднем сидении может сидеть человек любого веса, то тогда имеет смысл "выкинуть" N наибольших чисел из списка - этих людей мы посадим на передние сидения.
Тогда остальные M = N - K чисел надо будет попытаться разбить на тройки так, чтобы сумма каждой тройки не превышала 210 кг. А значит, сумма этих чисел, деленная на 210, даст нам третью оценку N3 количества машин, т.е. "точно не меньше чем столько". Если N3 > N, значит, нужно увеличить N и попытаться снова.

Однако реально может потребоваться больше, например, если у нас остались числа 90, 90, 90, 90, 60. Сумма даст 420, т.е. две машины, но легко увидеть, что реально понадобится больше, так как попытка подсадить человека на 60 кг в любую из машин даст перебор.

Искать тройки можно следующим образом. У нас осталось M чисел для распределения по тройкам.
Строим трёхмерный массив, где каждому измерению соответствует один человек из тройки. Значение ячейки 210 минус сумма весов этих людей. Тогда мы можем легко найти такую ячейку массива, которая ближе всего к нулю, но при этом положительная. Это будет "оптимальная" тройка, которая ближе всего к предельной нагрузке. Выкидываем из массива соответсвующие "срезы", т.е. исключаем эту тройку людей из рассмотрения, и ищем следующую тройку. А дальше есть два варианта.
Либо все элементы массива оказываются отрицательны - тогда оставшиеся люди не могут сформировать тройки, их нужно делить на пары по аналогии.
Либо у нас в массиве остаётся три или меньше элементов. В этом случае эти элементы формируют последнюю (возможно неполную) тройку.
Так или иначе, количество "троек" и "пар" должно совпасть с предполагаемым количеством N машин. Если их больше - нужно увеличить N и попытаться снова.

Стоит обратить внимание что массивы "троек" и "пар" будут симметричными, а потом достаточно считать только их часть.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы