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

Question

[Ярослав #]

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

Само задание:

Мой код который работает в 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)

Comments

[Алан Гибизов]

Эээ… по-моему, это не функция. Это винегрет с колбасой.

Там же чорт ногу сломит. Вы предлагаете это разбирать?
Если бы я решил в этом разобраться, разбил бы на множество мелких функций, каждая из которых делала бы своё дело. И поименовал бы внятно, что делает каждая функция. Неплохо функции также документировать и/или откомментировать.
Но делать за вас это неохота.

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

Answer 1

[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 и попытаться снова.

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

Comments

[Ярослав #]

Увидел в твоей идее много моментов из своей программы, но когда ты дошел до массивов понял, что в этом мой пробел. Пока еще не изучал их. Спасибо за ответ, попробую разобраться с массивами и реализовать.