我只是需要你的帮助。我正在使用 PHP 构建一个关于学术咨询的系统。基本上我需要一个关于如何实现系统主要功能的算法。主要思想是数组中有一个课程列表，我需要从该列表中获取所有可能的组合。每门课程都有一个指定其大小的单元/编号。算法应该根据一定的大小进行组合。
例如。
English - 1
Math - 3
Algebra - 3
History 3
Computer(lec) - 2
Computer(lab) - 1
最大尺寸 = 9。
所以算法应该在不超过大小限制的情况下获得所有组合。
所以结果可能是这样的。
(Math , Algebra , History ) the size is equal to 9
(History , Computer(lec), Computer(lab), Algebra)
(English , Computer(lec), Computer(lab), Algebra)
类似的东西。谢谢。我只是需要你的建议。
尝试这样的递归
<?php
$aviCourses = array(
"English"=>1,
"Math"=>3,
"Algebra"=>3,
"History"=>1,
"Computer(lec)"=>2,
"Computer(lab)"=>1
);
$foundCombinations = array();
function fillBucket($courses , $remainder ) {
global $aviCourses,$foundCombinations;
if($remainder < 0) return; //overfill
//else first of all put this compination in the list
$foundCombinations[] = $courses;
//for every avalable cource which is not in $courses yet
foreach(array_diff(array_keys($aviCourses),$courses) as $candidate) {
//call fill bucket recursive
fillBucket(
//append the candidate to the courses
array_merge($courses,array($candidate)),
//decrement the hours counter
$remainder-$aviCourses[$candidate]
);
}
}
fillBucket(array(),9);
//filter out the duplicates with different order of lectures
array_walk($foundCombinations, sort);
array_walk($foundCombinations, function(&$v){$v = implode($v,',');});
$foundCombinations = array_unique($foundCombinations);
sort($foundCombinations);
array_walk($foundCombinations, function(&$v){$v = explode(',',$v);});
//end filter out
print_R($foundCombinations);
试试这个：
$courses=array('English','Math','Algebra','History','Computer(lec)');
$sizes = array('1','3','3','3','2');
//maximum 6 hours
$limit=9;
//minimum number of 3 courses
$minimum=3;
$possible= array();
function get_comb($previous, $depth){
global $courses;
$count=count($courses);
global $possible;
global $sizes;
global $limit;
global $minimum;
if ($depth>$count){
$size_of_course=0;
foreach($previous as $nr=>$course){
if($course !== 0){
$size_of_course+=$sizes[$nr];
}
else{
//remove zeros
unset($previous[$nr]);
}
}
if ($size_of_course<=$limit&&count($previous)>=$minimum){
$possible[]=$previous;
}
return;
}
//either you have this course...
get_comb(array_merge($previous,array($courses[$depth-1])),$depth+1);
//or you dont..
get_comb(array_merge($previous,array(0)),$depth+1);
}
get_comb(array(),1);
//output
echo '<pre>';
var_dump($possible);
在前面的变量中，课程在函数递归时相加。
解释：首先，我计算所有可能的组合。为此，我将课程视为插槽：
whether you take the course or not, possibilities:
course a course b
yes yes
yes no
no yes
no no
这是通过这部分功能完成的。它是一个递归函数，因此它在函数内调用自身：
function get_comb($previous, $depth){
//either you have this course...
get_comb(array_merge($previous,array($courses[$depth-1])),$depth+1);
//or you dont..
get_comb(array_merge($previous,array(0)),$depth+1);
}
get_comb(array(),1);
假设：
$courses=array('course a','course b');
递归函数调用看起来像这样（0 表示，您不参加该课程）：http: //img43.imageshack.us/img43/5688/flowdiagram.png
之后，如果它们符合要求，我将可能性保存在 $possible: 因为 depth=3 和 count=2, $depth>$count 所以这部分代码开始发挥作用：
if ($depth>$count){
$size_of_course=0;
foreach($previous as $nr=>$course){
if($course !== 0){
//the index of $previous is the same as in $courses and $sizes, so
//$previous[1],$courses[1],$sizes[1] is logicaly referring to the same course
//add up all sizes of the courses that are used in this possibility
$size_of_course+=$sizes[$nr];
}
else{
//remove zeros
unset($previous[$nr]);
}
}
//the size of the course has to be lower or same as the size limit
//now without the zeros, count($previous) gives you the amount of courses taken in this possibility
if ($size_of_course<=$limit&&count($previous)>=$minimum){
//if it fits, save this possibility in the $possible array
$possible[]=$previous;
}
return;
}
希望我能帮助你。
- - - - - - - - - - - - - - - - - - - - - - -编辑 - - ----------------------------------
归档这个：'如果有计算机（lec），它只会在计算机（实验室）也存在的情况下接受它作为可能的组合'：替换$possible[]=$previous;为：
//further conditions are placed here
//IMPORTANT: the name of the courses down here (in_array('Computer(lec)') have to be EXACTLY the same as in the array $courses.
//e.g. if in $courses array the name is 'computer(lec)' and down here it's 'Computer(lec)' (uppercase) or 'computer (lec)' (space) it DOES NOT WORK!
//if Computer(lec) is present...
if(in_array('Computer(lec)',$previous)){
//Computer(lab) has to be present too
if(in_array('Computer(lab)',$previous)){
$possible[]=$previous;
}
else {
//if its not present dont save
//do nothing
}
}
else{
//if computer(lec) is not present, no problem, just save
$possible[]=$previous;
}
所以完成的代码将是
$courses=array('English','Math','Computer(lec)','Computer(lab)');
$sizes = array('1','1','2','2');
//maximum 6 hours
$limit=9;
//minimum 3 courses
$minimum=0;
$possible= array();
function get_comb($previous, $depth){
global $courses;
$count=count($courses);
global $possible;
global $sizes;
global $limit;
global $minimum;
//the end of the $courses array is reached
if ($depth>$count){
$size_of_course=0;
foreach($previous as $nr=>$course){
if($course !== 0){
//the index of $previous is the same as in $courses and $sizes, so
//$previous[1],$courses[1],$sizes[1] is logicaly referring to the same course
//add up all sizes of the courses that are used in this possibility
$size_of_course+=$sizes[$nr];
}
else{
//remove zeros
unset($previous[$nr]);
}
}
//the size of the course has to be lower or same as the size limit
//now without the zeros, count($previous) gives you the amount of courses taken in this possibility
if ($size_of_course<=$limit&&count($previous)>=$minimum){
//further conditions are placed here
//IMPORTANT: the name of the courses down here (in_array('Computer(lec)') have to be EXACTLY the same as in the array $courses.
//e.g. if in $courses array the name is 'computer(lec)' and down here it's 'Computer(lec)' (uppercase) or 'computer (lec)' (space) it DOES NOT WORK!
//if Computer(lec) is present...
if(in_array('Computer(lec)',$previous)){
//Computer(lab) has to be present too
if(in_array('Computer(lab)',$previous)){
$possible[]=$previous;
}
else {
//if its not present dont save
//do nothing
}
}
else{
//if computer(lec) is not present, no problem, just save
$possible[]=$previous;
}
}
return;
}
//either you have this course...
get_comb(array_merge($previous,array($courses[$depth-1])),$depth+1);
//or you dont..
get_comb(array_merge($previous,array(0)),$depth+1);
}
get_comb(array(),1);
//output
echo '<pre>';
var_dump($possible);