在php中为背包算法添加限制

Question

我需要这样的东西：算法选择球员与最大点，但在给定的成本

我理解背包的概念，我已经做了一个算法，使用0/1网格系统给出了最优解。问题是我没有弄清楚如何实施这些限制，我所说的限制是指每个位置只有X名球员。我不太明白阿米特在上面的链接中给出的答案。如果你能给我一些启发，那就太棒了。

提前感谢，抱歉我的英语。

编辑：很抱歉信息不足。这是我的第一个问题：）

以下是我到目前为止所做的。

$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
)
*/

现在我需要限制这个阵型，每个位置（PG、SG、SF、PF）只有2名球员，C位置只有1名球员，以获得最佳的9人阵容。

Answer 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'];
        }
    }
}