Add restriction to a Knapsack algorithm in php

Question

I need something like this: Algorithm to select Player with max points but with a given cost

I understand the concept of knapsack and I already made an algorithm that gives me the optimal solution using the 0/1 grid system. The problem is that i'm not figuring out how to implement the restrictions and by restrictions I mean only X players for each position. I do not quite understand the answer given by amit in the link above. If you could give me some enlightenment it would be awesome.

Thanks in advance and sorry for my english.

EDIT: Sorry for the lack of information. This is my first question :)

Here is what I've done so far.

$all_players = array();

foreach ($arr_players as $value) {

    $all_players[] = array( "name" => $value['name'],
                            "position" => $value['position'],
                            "salary" => $value['salary'],
                            "score" => $value['score']
                            );

}  //  array sorted by salary


$total_players = count($all_players);
$salary_cap = 601;

//  using the knapsack 0/1 grid method
for ($x = 0; $x < $total_players; $x++) {
    for ($y = 1; $y < $salary_cap; $y++) {
        if ($x == 0) {

            $score_arr[$x][$y] = 0;
            $keep_arr[$x][$y] = 0;

        } else {

            if ($all_players[$x]['salary'] <= $y) {

                $arr_pos = $x - 1;
                $salary_left = $y - $all_players[$x]['salary'];

                if ($all_players[$x]['salary'] == $y) {
                    $score_pres = $all_players[$x]['score'];
                } else {
                    $score_pres = $all_players[$x]['score'] + $score_arr[$arr_pos][$salary_left];
                }

                $score_prev = $score_arr[$arr_pos][$y];

                if ($score_pres > $score_prev) {
                    $score_arr[$x][$y] = $score_pres;
                    $keep_arr[$x][$y] = 1;
                } else {
                    $score_arr[$x][$y] = $score_prev;
                    $keep_arr[$x][$y] = 0;
                }

            } else {

                $score_arr[$x][$y] = 0;
                $keep_arr[$x][$y] = 0;

            }
        }
    }
}


$total_players = $total_players - 1;
$salary_left = 600;
$best_lineup = array();

//
for ($x = $total_players; $x > -1; $x--) {
    if ($keep_arr[$x][$salary_left] == 1) {

        $best_lineup[] = $all_players[$x]['name'];
        $salary_left = $salary_left - $all_players[$x]['salary'];

    }
}

/////////////////////////////////////////////////
/*
The output:

Array
(
    [0] => Ramon Sessions  //  PG
    [1] => Omri Casspi  //  SF
    [2] => D.J. Augustin  //  PG
    [3] => Steven Adams  //  C
    [4] => Zach LaVine  //  PG
    [5] => Kris Humphries  //  PF
    [6] => Isaiah Canaan  //  PG
    [7] => Corey Brewer  //  SF
    [8] => Rodney Stuckey  //  SG
    [9] => O.J. Mayo  //  SG
    [10] => Greg Monroe  //  PF
    [11] => DeMarcus Cousins  //  C
)
*/

Now I need to restrict this array to have only 2 players from each position (PG, SG, SF, PF) and 1 from C position for the best 9 player lineup.

Please present the problem, what you have tried so far, and what it is that you do not understand. — Sverri M. Olsen, Nov 28 '14 at 01:03

Michael D. · Answer 1 · 2014-11-28T10:55:28.573

1

//  team position with wanted amount of players
$team = array("PG" => 2, "SG"  => 2, "SF"  => 2, "PF"  => 2, "C"  => 1);

$x = $total_players;
$salary_left = 600;
$best_lineup = array();

//
while (--$x >  -1) {
    if ($keep_arr[$x][$salary_left] == 1) {

        $pos = $all_players[$x]['position'];
        if ($team[$pos] > 0) {
            //  we need another player for that pos
            $team[$pos]--; // same as $team[$pos] = $team[$pos] -1;

            $best_lineup[] = $all_players[$x]['name'];
            $salary_left = $salary_left - $all_players[$x]['salary'];
        }
    }
}

edited Nov 28 '14 at 10:55

answered Nov 28 '14 at 02:25

Michael D.

1,795
2
18
25

Thank you. You're code is way more cleaner than mine and you're obviously a better coder than I am. Apologize for that. I'm not used to work with objects. However I updated the code with your sugestions. It would be great if, maybe, you could help. – moft Nov 28 '14 at 04:10
I've changed my answer, hope that helps – Michael D. Nov 28 '14 at 10:56
Thank you for your time and answer. Well, I already tried that and although I get a combination I don't get the best possible combination. If I run the problem through brute force with some of the high score iterations I get an array of 9 players where total score is way bigger. Brute force is a solution but takes way too long. Other problem with this solution is that it restricts the lineup PGs < 2 and not PGs == 2. One thing I don't mentioned: $all_players array is sorted by salary. Relly stuck in this one. – moft Nov 28 '14 at 16:55

Add restriction to a Knapsack algorithm in php

1 Answers1