Paul Kellerman
14.12.2012, 14:27
Уважаемые коллеги!
Многие из вас пишут рабочие программы, разбираются с нагрузкой
преподавателей и прочие вещи, где возникает следующая задача:
Имеется список целых неотрицательных чисел W =
(в нашем случае они означают набор часов, разложенных по кате-
гориям по критериям - дисциплины, формы обучения, вид занятий)
Сумма чисел исходного списка равна: 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
В результате вычисляется список подсписков индексов
"подходящих" часов, расположенных в исходном списке.
[B]
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}]
Многие из вас пишут рабочие программы, разбираются с нагрузкой
преподавателей и прочие вещи, где возникает следующая задача:
Имеется список целых неотрицательных чисел W =
(в нашем случае они означают набор часов, разложенных по кате-
гориям по критериям - дисциплины, формы обучения, вид занятий)
Сумма чисел исходного списка равна: 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
В результате вычисляется список подсписков индексов
"подходящих" часов, расположенных в исходном списке.
[B]
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}]