在 php 中为背包算法添加限制 - Add restriction to a Knapsack algorithm in php

Add restriction to a Knapsack algorithm in php

本文关键字：添加算法背包 php | 更新日期: 2023-09-27

>我需要这样的东西：选择具有最高点数但具有给定成本的玩家的算法

我

了解背包的概念，并且我已经制作了一个算法，该算法可以使用 0/1 网格系统为我提供最佳解决方案。问题是我没有弄清楚如何实施限制，我所说的限制是指每个位置只有 X 名球员。我不太明白 amit 在上面的链接中给出的答案。如果你能给我一些启发，那就太棒了。

提前感谢，对不起我的英语。

编辑：很抱歉缺少信息。这是我的第一个问题:)

这是我到目前为止所做的。

$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 名球员阵容。

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