Здравствуйте! В сети есть книга "Грокаем алгоритмы", в ней описана похожая на Вашу задача (задача про рюкзак).

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

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

Это уже следующий уровень решения, построение оптимальных маршрутов перемещения

Всем привет! Занимаюсь планированием распределения детей в пункты проведения экзаменов, с Питоном знаком слабо, поэтому подскажите, в какую сторону копать. Дано - 9 пунктов, с разной вместимостью, у каждого - свой код и своя вместимость. При распределении детей участники из конкретной школы, если она является пунктом проведения экзаменов, идут сдавать у себя, у них приоритет, вместимость пункта уменьшается на эту величину. Оставшихся участников надо равномерно распределить по пунктам. Плюс у программы должна быть возможность перераспределения участников вручную. Количество участников из всех школ разное, разумеется, т.е. тут надо перебирать значения. Может есть какое-то готовое решение?

Всем привет! Занимаюсь планированием распределения детей в пункты проведения экзаменов, с Питоном знаком слабо, поэтому подскажите, в какую сторону копать. Дано - 9 пунктов, с разной вместимостью, у каждого - свой код и своя вместимость. При распределении детей участники из конкретной школы, если она является пунктом проведения экзаменов, идут сдавать у себя, у них приоритет, вместимость пункта уменьшается на эту величину. Оставшихся участников надо равномерно распределить по пунктам. Плюс у программы должна быть возможность перераспределения участников вручную. Количество участников из всех школ разное, разумеется, т.е. тут надо перебирать значения. Может есть какое-то готовое решение?

Чтобы сделать что-то для государства нужно мыслить, как государство.
Реально нужно относиться к заданиям. Вот на самом деле  алгоритм, реализация которого выиграет любой тендер на госзакупках:
участников раскидать по пунктам рандомно;
участники сдают экзамен в пунктах проведения экзаменов, находящихся на максимальном расстоянии от проживания участников;
пункт проведения экзаменов не должен оказаться школой в которой учится участник.

Все верно. Плюс еще нельзя, чтобы в качестве организаторов в аудитории оказались учителя-предметники и/или учителя (родители) участников ГИА. Проблема в том, что централизованной системы такого распределения не существует, насколько я знаю, каждый регион решает такую задачу по-своему, из-за чего каждый год Рособрнадзор выявляет кучу нарушений. Это должно решаться на уровне Федерации. А пока распределяем ручками

Все верно. Плюс еще нельзя, чтобы в качестве организаторов в аудитории оказались учителя-предметники и/или учителя (родители) участников ГИА. Проблема в том, что централизованной системы такого распределения не существует, насколько я знаю, каждый регион решает такую задачу по-своему, из-за чего каждый год Рособрнадзор выявляет кучу нарушений. Это должно решаться на уровне Федерации. А пока распределяем ручками

Кстати, почему это не вид рюкзака:

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

Кстати, почему это не вид рюкзака:

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

Просто даже если представить это в таком виде и каждому ученику присвоить ценность обратно пропорциональную расстоянию до школы, то выйдет так, что каждый рюкзак поочередно будет наполняться ближайшими к нему учениками до отказа не обращая внимания на другие "рюкзаки'. Так мы не берём во внимание общий пройденный учениками путь и выйдет так что независимо максимизируя ценность одного "рюкзака" мы можем увеличить общий пройденный путь.

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

Проблема в том что есть N школ (рюкзаков) и все они наполняются из одного набора учеников. Тут нужно минимизировать общее пройденное расстояние. К примеру начнёшь ты заполнять один рюкзак обходя граф. Взял всех учеников с точки X потом часть из Y. При этом, когда будешь заполнять другой рюкзак, к которому Y были ближе, тебе будет недостаточно учеников с Y(так как часть ты уже забрал) и ты полезешь в точку Z. Так ты будешь максимизировать ценность рюкзаков поодиночке но в общем это может выйти далеко не оптимально.