Комбинации школ из 50 и 25 мест для 100 учеников

[gris]

(Оффтоп)

Joker_vD, какой райцентр? Какие свиньи?
Вы определённо не в теме
Это же олигархическая деревня. Там и школы элитные, специализированные. На 25 персон. При этом персонала человек 200. В классе 3-4 ученика. Урок ведут одновременно 6 преподавателей, психолог, юрист, гувернёры и гувернантки. Ну и прочая обслуга. Преподаватели одеты и загримированы соответственно теме урока. Геометрию ведут Пифагор с Эвклидом, физику — Эйнштейн и Паскаль. На уроки зоологии приводят изучаемых животных. У каждой школы своя обсерватория, спортивный комплекс. Поле для гольфа вот одно на всех.

А что такое аморфная задача?
Я думал, Вы всерьёз про амфорную. Это название действительно было в Древней Греции. Вино и масло разливали в амфоры и надо было для определённого объёма жидкости подобрать набор амфор, в которые она бы вместилась. По существу, это и есть Ваша задача. Диофант Александрийский и начал свои исследования с амфорных задач. Но там была ещё куча особенностей, связанных с "требованиями богов". Например, он уже использовал то, что при заданной форме объём амфоры зависит от куба размера, а площадь расписываемой поверхности от квадрата.

Ну в общем, теория этих задач уже достаточна развита в линейном программировании.

+++ Я имел в виду тему http://dxdy.ru/topic43521.html

[bigarcus]

Да не, это я пример попробовал составить жизненный. Говорю же задача аморфная. В начальном сообщении я формулировал с автобусами: как рассадить такое-то количество людей по стольким-то таким-то типам автобусов.

-- Сб июн 23, 2012 13:51:31 --

Поискал по форуму. Нашел только новое сообщение нового участника, без ответов: http://dxdy.ru/topic60253.html. Но Он спрашивает про точное равенство, а в моей задаче действительно перекрываться могут числа и даже должны, если не слишком сильно.

[gris]

Вы хотите решить три разные задачи.
Первая: найти число натуральных (с нулём) решений некоторого диофантового уравнения (двойного неравенства).

Вторая: построить некоторый алгоритм, который построит все эти решения.

Третья: найти на множестве решений экстремум некоторой функции.

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

Например, в задаче нахождения максимума функции $f(n,m)=64+243n-3n^2+310m-4m^2$ для натуральных $n, m: n+m=499$ нет необходимости проверять все 500 вариантов.

[bigarcus]

А как составить из начальных данных функцию, максимум которой потом искать?

[gris]

Вот для этого и нужно вначале разработать математическую модель задачи.
На примере школ. У нас есть три варианта: 50+50, 50+25+25, 25+25+25+25, но как из сравнивать?
В реальной жизни, естественно, влияют и расположение школ, и стоимость их постройки и куча других параметров, но у Вас же упрощённая модель. То есть желательно оценить каждый вариант одним числом, получающимся по некоторой формуле.
Возможно, каждая 50-местная школа приносит 3 очка, а 25-местная — 2. Тогда варианты оцениваются в 6, 7 и 8 очков. Побеждает третий.
А если каждая 50-местная школа приносит 5 очков, а 25-местная — 2, то варианты оцениваются в 10, 9 и 8 очков. Побеждает первый.

[bigarcus]

gris в сообщении #588264 писал(а):

У нас есть три варианта: 50+50, 50+25+25, 25+25+25+25, но как из сравнивать?

Прежде чем сравнивать я хочу их получить. Понятно, что в этом примере легко устно увидеть всевозможные требуемые разбиения, но а если бы типов автобусов (или школ) было больше (хотя в моей практической задаче, которую я пытаюсь решить, их не больше трех). Есть ли какая-то формула, не знаю, комбинаторная что ли...?

[gris]

Формула чего? Количества решений? Зачем Вам количество?
Формулу каждого варианта в зависимости от его номера? Мне кажется, что она если и существует, то настолько же пригодна, как формула n-ного простого числа.
Вы бы уж показали свою практическую задачу.

[bigarcus]

Формула не количества решений, а сами решения - те варианты, на которое одно число можно разложить на другие.

Вот число 100 имея для чисел 25 и 50 можно разложить тремя способами. Я хочу формулу, которая бы показывала эти возможные варианты, а не я сам догадывался.

(Оффтоп)

Представьте очень большое число и много маленьких чисел. Требуется представить варианты разложения большого числа на маленькие.

[gris]

Да я понимаю.
Можно составить алгоритм, а наверняка он уже и описан достаточно подробно, по которому будут подбираться варианты, потом оцениваться. Но их может быть очень много, особенно при приближённом равенстве суммы.
А если целевая функция хорошая (выпуклая, линейная), то не будет необходимости их все рассматривать.
Вот пример: разменять миллион плюс-минус сто рублей старинными монетами в 1,2,3 и 5 коп. Сколько там вариантов? Уж наверняка много.
А надо, например, минимизировать совокупную себестоимость всех монет (а себестоимость однотипных монет не прямо пропорциональна их номиналу). Или совокупную разность между количеством монет разных номиналов. В этом случае задачу можно и врукопашную решить.

[bigarcus]

gris в сообщении #588278 писал(а):

Можно составить алгоритм, а наверняка он уже и описан достаточно подробно, по которому будут подбираться варианты, потом оцениваться.

К сожалению, я не знаю как составить алгоритм и не знаю где он описан.

gris в сообщении #588278 писал(а):

Но их может быть очень много, особенно при приближённом равенстве суммы.

Да, мне нужно именно приближенное равенство. Но не думаю что вариантов уж слишком много. Опишу чуть ближе к делу форму задачи.

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

gris в сообщении #588278 писал(а):

А если целевая функция хорошая (выпуклая, линейная), то не будет необходимости их все рассматривать.

Ну, хотелось бы по шагам. Сначала получить варианты на первом шаге. А на втором уж выбирать.

[gris]

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

[bigarcus]

Да, да, да! Но как хоть пустяк-то решить?

[gris]

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

Вот Вам пример. Разложить примерно тысячу на слагаемые 27, 59 и 134.

N=1000; K=0;
m1=27; m2=59; m3=134;
for (k1=0;k1<40;k1++) {
   for (k2=0;k2<17;k2++) {
      for (k3=0;k3<9;k3++) {
         NK=k1*m1+k2*m2+k3*m3;
          if (Math.abs(NK-N)<3) {K=K+1;trace (NK+"="+k1+"*"+m1+"+"+k2+"*"+m2+"+"+k3+"*"+m3)}
}}}
trace ("Всего "+K+" вариантов")

998=2*27+16*59+0*134
998=3*27+11*59+2*134
998=4*27+6*59+4*134
998=5*27+1*59+6*134
999=8*27+11*59+1*134
999=9*27+6*59+3*134
999=10*27+1*59+5*134
1000=13*27+11*59+0*134
1000=14*27+6*59+2*134
1000=15*27+1*59+4*134
1001=19*27+6*59+1*134
1001=20*27+1*59+3*134
1002=24*27+6*59+0*134
1002=25*27+1*59+2*134
998=32*27+0*59+1*134
999=37*27+0*59+0*134
Всего 16 вариантов

[bigarcus]

Ой как здорово, вот это да!!! Я думал как написать что-то подобное, но у меня не получилось( А у в вашем коде даже учитывается не только точное разложение, но и близкое к 1000!

-- Вс июн 24, 2012 01:33:31 --

Я только не понял откуда эти ограничители взялись, откуда эти цифры:

k1<40;
k2<17;
k3<9;

и ещё хотел спросить на каком языке ваш код? Я только Паскаль обыкновенный знаю, но если пойму алгоритм, то переложить смогу, но все равно интересно где такой элегантный код пишется?

-- Вс июн 24, 2012 01:35:16 --

gris в сообщении #588305 писал(а):

Всего 16 вариантов

Алгоритм же 15 выдал, откуда 16?

-- Вс июн 24, 2012 01:37:45 --

Я правильно понял, что вы именно следующим:

gris в сообщении #588305 писал(а):

Math.abs(NK-N)<3)

указали чтобы и близкие к 1000 (от 1998 до 1002) разложения проделывал, да?

[Joker_vD]

(Оффтоп)

Это Си/Си++, и элегантного в этом языке мало.