Комбинаторика в учебно-методической работе

[Paul Kellerman]

Уважаемые коллеги!

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

Имеется список целых неотрицательных чисел W = [B1, B2,..., Bn]
(в нашем случае они означают набор часов, разложенных по кате-
гориям по критериям - дисциплины, формы обучения, вид занятий)

Сумма чисел исходного списка равна: B1 + B2 + ... + Bn = S.

Задан список подсумм [V1, V2,..., Vm], причем m < n и V1 + V2 +...+ Vm = S.

Необходимо "раскидать" числа из исходного списка W по m непустым подспис-
кам L1...Lm, так чтобы сумма чисел в каждом j-м подсписке Lj была равна Vj.

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

Это давно известная комбинаторная задача. Но интересно, как вы ее решаете.

Я тут не поленился, немного почитав про комбинаторику и рекурсию накидал на
встроенном в математический программный пакет Maple алгоритм, который пол-
ным перебором находит разбиение, если оно существует при заданных условиях.
Писать полноценную Windows-программу, если честно было лень. Поэтому кому
интересно, установите себе Maple 15 и вставьте туда нижеприведенный скрипт.

Исходный набор часов задается в списке BaseList
Набор условий (подсумм) задается в списке SumsList

В результате вычисляется список подсписков индексов
"подходящих" часов, расположенных в исходном списке.


restart:
with(combinat):
with(plottools):
with(plots):

# Recursive algorithm for decomposing base list of values
# to list of subsets where sum of values in subsets are
# equal to summary given in the list of the summaries
# by Paul Kellerman. (Full search algorithm, 2012)

RecFunc:= proc(BL,SL,fast,BI,SI,res)
local i,temp,SS,BISS,r_res,r_BI,r_SI,l_flag:
global n,m,count,g_res,g_flag:
if ((nops(BI) > 0) and (nops(SI) > 0) and (g_flag = 0)) then
BISS:= subsets(BI):
while (not(BISS[finished]) and (g_flag = 0)) do
SS:= BISS[nextvalue]():
if (nops(SS) > 0) then
count:= count + 1:
temp:= 0:
for i in SS do
temp:= temp + BL[i]:
end do:
if (temp = SL[SI[1]]) then
r_BI:= BI:
for i in SS do
r_BI:= r_BI minus {i}:
end do:
r_SI:= SI minus {SI[1]}:
r_res:= [op(res),SS]:
if (nops(r_res) = m) then
g_res:= r_res:
g_flag:= 1:
end if:
RecFunc(BL,SL,fast,r_BI,r_SI,r_res):
end if:
end if:
end do:
end if:
end proc:

MainFunc:= proc(BL,SL,fast)
local b_BI,b_SI,b_res:
global n,m,count,g_res,g_flag:
n:= nops(BL):
m:= nops(SL):
if ((n > 0) and (m > 0) and (n >= m)) then
count:= 0:
g_res:= []:
g_flag:= 0:
b_BI:= {seq(i,i=1..n)}:
b_SI:= {seq(i,i=1..m)}:
b_res:= []:
RecFunc(BL,SL,fast,b_BI,b_SI,b_res):
return(g_res):
end if:
end proc:

# Example of decomposition

BaseList:= [98,61,59,52,156,17,65,170,32,24,43,30,17,11,17,88, 51,41,65,78];
SumsList:= [87,218,870];

temp:= 0:
for i in BaseList do
temp:= temp + i:
end do:
basetotal:= temp;

temp:= 0:
for i in SumsList do
temp:= temp + i:
end do:
sumstotal:= temp;

results:= MainFunc(BaseList,SumsList,0);



[{3,6,14},{1,9,16},{2,4,5,7,8,10,11,12,13,15,17,18, 19,20}]

[0647]

Сообщение от Paul Kellerman

интересно, как вы ее решаете.

Да как нагрузку не верстай - все равно порежут и перекрыжат, исходя из фонда оплаты труда... А если серьезно, то когда приходилось делать подобное на кафедре, то как ни смешно (я по диплому - прикладной математик), делал все на глаз - не считая мелких арифметических расчетов и логических проверок в Экселе. В частности (для примера) - раскидать, ну пусть 18 часов лекционных на 11 тем мне поможет не комбинаторика, а знание (априорное + апостериорное ), насколько трудна та или иная тема и насколько в этом учебном году тупые студенты.

[Paul Kellerman]

Сообщение от 0647

раскидать, ну пусть 18 часов лекционных на 11 тем

Сообщение от 0647

делал все на глаз

В этом случае понятно, что на глаз, ибо условие одно единственное, сумма часов по
всем 11 темам должна равняться 18. В других случаях условий может быть множество.

[Hogfather]

Сообщение от Paul Kellerman

Maple 15

I don't understand barbarian languages! Speak BASIC with comments!

Сообщение от Paul Kellerman

который полным перебором находит разбиение, если оно существует при заданных условиях

Ну, так не интересно. А еcли строгое решение не существует, а надо найти наилучшее из возможных? Как Вам идея МНК?

[Paul Kellerman]

Сообщение от Hogfather

А еcли строгое решение не существует, а надо найти наилучшее из возможных?

Лично у меня есть разработанная еще при написании диссертации программа
для поиска распределения множества потребителей вычислительных ресурсов
по множеству поставщиков ресурсов. Она использует смесь жадного алгоритма,
случайного поиска и локального поиска с управляемым радиусом поисковых зон.
Программа за примелемое время находит субоптимальное распределение потре-
бителей по поставщикам. В нашем случае тип ресурса один - это часы. Исходный
набор чисел - требования потребителей, а набор условий - ресурсы поставщиков.

Сообщение от Hogfather

Как Вам идея МНК?

Матрица распределения - строго булевая. Вещественные решения - неприемлемы.