Программа, которая выбирает лучшее из 10

Question

Мне нужно сделать программу на python, которая выбирает машины из массива, который заполнен массой из 10 машин. Идея состоит в том, что он заполняет баржу, которая может наиболее эффективно удерживать ~ 8 тонн, а минимальное пространство остается незаполненным. Моя идея состоит в том, что он делает вариации масс и выбирает тот, который ближе всего к максимальному весу. Но так как я новичок в алгоритмах, я понятия не имею, как это сделать

Answer 1

Я бы решил это упражнение с помощью динамического программирования. Вы должны быть в состоянии получить оптимальное решение в O (m * n) операциях (n от количества автомобилей, m от общей массы). Однако это будет работать только в том случае, если все массы целые.

Как правило, у вас есть проблема двоичного линейного программирования. Это очень сложно в целом (NP-полная).

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

Answer 2

Это проблема упаковки 1D бункера. Это проблема NP, и нет оптимального решения. Однако есть способ решить эту проблему с помощью жадного алгоритма. Скорее всего, вы захотите попробовать мой решатель бин-упаковки на phpclasses.org (бин-упаковка).

Если у меня есть не взвешенный и ненаправленный график, и каждый узел связан с каким узлом, то у меня есть (n ^ 2-n) / 2 пары узлов и общее число n / 2-n возможностей / комбинаций:

1,2,3,4,5,...,64
2,1,X,X,X,...,X
3,X,1,X,X,...,X
4,X,X,1,X,...,X
5,X,X,X,1,...,X
.,X,X,X,X,1,.,X
.,X,X,X,X,X,1,X
64,X,X,X,X,X,X,1 

Разве это не то же самое с 10 машинами? (45 пар машин и 90 комбинаций / возможностей). Я что-то забыл? Где ошибка?

Answer 3

Подобная вам проблема похожа на классическую задачу коммивояжера, которая требует от продавца наиболее эффективного способа посещения списка городов.Разница в том, что вполне возможно, что вам не понадобится каждый автомобиль, чтобы заполнить баржу, тогда как продавец должен посетить каждый город.Но проблема похожа.Грубым способом решения этой проблемы является исследование каждой возможной комбинации автомобилей, от 1 до 10 автомобилей. Мы будем считать, что допустимо иметь любое количество каждого автомобиля (т. Е. Если автомобиль 2 является Ford Focus, выможет быть три форд фочи).Однако это легко изменить, если список автомобилей представляет собой точный список конкретных автомобилей, и вы можете использовать только 1 из них.

Теперь это быстро начинает занимать много времени.По мере того, как количество автомобилей увеличивается, количество возможных комбинаций автомобилей увеличивается геометрически, что означает, что при меньшем количестве, чем вы ожидаете, для запуска программы потребуется больше времени, чем в вашей жизни.Тем не менее, 10 должны быть управляемыми (получается чуть более 700 000 комбинаций, или 1024, если вы можете иметь только один из каждого предмета).

Прежде всего необходимо определить вес каждого автомобиля имаксимальный вес, который может выдержать баржа.

weights = [1, 2, 1, 3, 1, 2, 2, 4, 1, 2, 2]
capacity = 8

Теперь нам нужен способ найти каждую возможную комбинацию.Модуль Python itertools имеет функцию, которая даст нам каждую комбинацию заданной длины, но мы хотим, чтобы все длины.Итак, мы напишем один цикл, который идет от 1 до 10 и вызывает itertools.combinations_with_replacement для каждой длины.Затем мы можем узнать общий вес каждой комбинации, и если он будет больше, чем какой-либо вес, который мы уже нашли, но все еще в пределах емкости, мы запомним его как лучший из найденных нами.

Единственный реальный трюк в том, что нам не нужны комбинации весов - нам нужны комбинации индексов весов, потому что в конце мы хотим знать, какие машины ставить на баржу, а не их вес.Так что combinations_with_replacements(range(10), ...), а не combinations_with_replacements(weights, ...).Внутри цикла вы захотите получить вес каждого автомобиля в комбинации с weights[i], чтобы подвести его.

У меня изначально был код, но я его снял, так как это домашняя работа.:-) (Первоначально он не был помечен как таковой, но я должен был знать - я виноват в изменении времени.)

Если вы хотите разрешить только одну машину, вы должны использовать itertools.combinations вместо combinations_with_replacement.

Возможен ярлык, поскольку в другом месте вы упоминаете, что автомобили весят от 1 до 2 тонн.Это означает, что вы знаете , вам понадобится как минимум 4 из них (4 * 2 = 8), поэтому вы можете пропустить все комбинации из 1-3 машин.Тем не менее, это не будет обобщать, если проф изменил параметры на вас.