Трудности с перестановочным заданием на программирование «Козлов» в Python

Question

Мне была поставлена ​​задача - решить следующую задачу программирования:

Козы
Джордж со своим стадом коз на берегу реки. Он хочет пройти через реку со своими козами, используя плот с ограниченной грузоподъемностью, не более чем K курсов. У него все козлы разные, с разным весом. Он хочет подсчитать, какова минимальная вместимость плота, которая могла бы пройти всех его N коз через реку с не более чем K курсами.
Однако у него есть правила, которые он должен соблюдать:
В каждом курсе он сначала кладет на плот самый тяжелый из имеющихся козлов, затем из оставшихся он снова кладет самого тяжелого козла, который не будет слишком тяжелым для вместимости плота, затем следующего и так далее, пока не останется больше коз, которые могут пойти на плоту из-за его вместимости. После этого он доставляет их на другой берег (делает курс) и возвращается, чтобы получить больше коз на плоту и пройти другой курс. (Вместимость плота должна быть не меньше, чем вес самого тяжелого козла)

Таким образом, мне нужно написать скрипт, который вычисляет минимальную вместимость плота с заданным количеством курсов K , количество коз N и вес каждый из них ( А1, А2 и т. д.). Поскольку Джордж является относительно небольшой константой, вес Джорджа игнорируется (нет необходимости добавлять его в расчеты).

Все, что было отмечено до сих пор, соответствует требованиям испытания.

Пример результата правильного решения:

6 коз, 2 блюда
Вес каждой козы: 26, 7, 10, 30, 5, 4
Результат (минимальная вместимость плота): 42
Курсы: (30, 10); (26, 7, 5, 4)
Следующее решение не следует правилам: (30, 7, 4); (26, 10, 5) - потому что коза, которая весит 10 кг, может быть в первом курсе и должна быть там согласно правилам.

Моя попытка решения:

import itertools

goatnum = 0
courses = 0
goatw = []
counter = 0

goatnum = int(input("Enter the number of goats: "))
courses = int(input("Enter the number of courses: "))
for g in range(goatnum):
    goatw.append(int(input("Enter the weight of goat #{}: ".format(g+1))))

goatw = sorted(goatw, reverse=True)
goats = sum(goatw)
result = []
permlen = len(goatw)/courses
while not result:
    result = [seq for i in range(len(goatw), 0, -1) for seq in itertools.permutations(goatw, permlen) if sum(seq) == int(goats/courses)]
    if not result:
        goats += 1
        permlen += 1
    else:
        break

print(result)

Я использую перестановки для этой задачи просто потому, что не знаю другого способа ее решения. В настоящее время из результата я получаю только решения, которые не соответствуют правилам (для данного примера). Я получаю решение (30, 7, 4); (26, 10, 5) изнутри, однако, нет даже результатов с курсом, в котором количество коз отличается от 3, все курсы с 3 козами.

Мой вывод для данного примера (6 коз, 2 курса, ш: 26,7,10,30,5,4):

[(30, 7, 4), (30, 4, 7), (26, 10, 5), (26, 5, 10), (10, 26, 5), (10, 5, 26), (7, 30, 4), (7, 4, 30), (5, 26, 10), (5, 10, 26), (4, 30, 7), (4, 7, 30), (30, 7, 4), (30, 4, 7), (26, 10, 5), (26, 5, 10), (10, 26, 5), (10, 5, 26), (7, 30, 4), (7, 4, 30), (5, 26, 10), (5, 10, 26), (4, 30, 7), (4, 7, 30), (30, 7, 4), (30, 4, 7), (26, 10, 5), (26, 5, 10), (10, 26, 5), (10, 5, 26), (7, 30, 4), (7, 4, 30), (5, 26, 10), (5, 10, 26), (4, 30, 7), (4, 7, 30), (30, 7, 4), (30, 4, 7), (26, 10, 5), (26, 5, 10), (10, 26, 5), (10, 5, 26), (7, 30, 4), (7, 4, 30), (5, 26, 10), (5, 10, 26), (4, 30, 7), (4, 7, 30), (30, 7, 4), (30, 4, 7), (26, 10, 5), (26, 5, 10), (10, 26, 5), (10, 5, 26), (7, 30, 4), (7, 4, 30), (5, 26, 10), (5, 10, 26), (4, 30, 7), (4, 7, 30), (30, 7, 4), (30, 4, 7), (26, 10, 5), (26, 5, 10), (10, 26, 5), (10, 5, 26), (7, 30, 4), (7, 4, 30), (5, 26, 10), (5, 10, 26), (4, 30, 7), (4, 7, 30)]

Я новичок в этом, и я также получил пример использования перестановок из Интернета. Где мой код не так? Я знаю, что могу просто сделать функцию, чтобы проверить, соответствуют ли мои результаты правилам, и если нет, исправить результаты, но я не знаю, как это сделать. Любая помощь будет оценена.

Answer 1

Я считаю, что проблема, с которой вы столкнулись, состоит в том, что все перестановки, которые вы генерируете, состоят из 3 коз.Если бы вы сгенерировали все возможные перестановки из N коз, а затем нарезали эти перестановки в K местах, правильное решение было бы среди одного из этих списков.Например, с 3 козами A, B и C мы получаем следующие перестановки:

(A,B,C), (A,C,B), (B,A,C), (B,C,A), (C,B,A), (C,A,B)

Допустим, у нас есть 2 курса.Теперь представьте, что у нас есть K - 1 палка (1 в данном случае), которую мы можем поместить в N - 1 место (в нашем случае 2) в каждой из этих перестановок.Палка может быть помещена между любыми козами или по краям.Палка служит разделителем, определяющим, какие группы коз будут отправляться в каждой поездке.В общем случае у вас есть K - 1 палок для размещения, и вы не хотите помещать две палки в одно и то же место, поскольку это будет означать, что у вас будет одна поездка, когда на лодке нет коз.Затем мы получаем следующее пространство, в котором мы можем искать решение:

(A | B C), (A B | C)
(A | C B), (A C | B) 
(B | A C), (B A | C)
(B | C A), (B C | A)
(C | B A), (C B | A)
(C | A B), (C A | B)

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

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

Итак, в заключение,Один из способов решения этой проблемы с использованием перестановок:

1. Создание всех возможных перестановок коз.

2. Создание всех способов, которыми каждая перестановка можетразделить на K групп.

3. Избавиться от любого из кандидатов, сгенерированных на шаге 2, которые не соблюдают правила.

4. Из оставшихся кандидатов найдите ту, где самая тяжелая поездка легче, чем самая тяжелая поездка из других кандидатов.

Это ни в коем случае не оптимальное решение, но оно должно делать свою работу.