1

私はあなたの助けが必要です。アカデミックアドバイジングについて 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)

そんな感じ。ありがとう。あなたのアドバイスが必要です。

4

2 に答える 2

0

このような再帰を試してください

<?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);
于 2012-12-26T13:06:07.313 に答える
0

これを試して：

$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;
}

お役に立てれば幸いです。

- - - - - - - - - - - - - - - - - - - - - - -編集 - - ----------------------------------

これをアーカイブするには: 「computer(lec) がある場合、computer(lab) も存在する場合にのみ可能な組み合わせとしてそれを受け入れます」: 次のように置き換え$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);
于 2012-12-26T14:34:12.010 に答える