帮忙看下这题的算法..分够多,尽管来.

Question

NBA球员有两个属性,身价,所得的分数,现在以n元钱在500个球员中购买5个球员,
要求,5个球员的分数最大,而且身价总和<n据说这题很简单,惭愧!!!!

Answer 1

OMG, 这个算法够呛！google面试题？

Answer 2

随便取5个人只要身价<n ，然后在分别去比较，然后循环查找每个身价比他低，但是分数比他高的人，就替换他
不知道这样可以不

Answer 3

要解决一个问题
比如A性价比最高，买了A，余下的钱不够买任何一个球员但是不买A，可以买2个次性价比……，应该能凑出数字，超过A的。

Answer 4

/*
NBA球员有两个属性,身价,所得的分数,现在以n元钱在500个球员中购买5个球员,
要求,5个球员的分数最大,而且身价总和<n
*/
for($i = 0; $i < 500; $i++){ for($j = 0; $j < $i; $j++){

for($k = 0; $k < $j; $k++){

for($k = 0; $k < $j; $k++){

for($k = 0; $k < $j; $k++){

//假设球员有ID，那么三层循环中的$i、$j、$k皆为球员的ID，(买几位就有几个循环)如此能够保证所有的组合出现，将所有组合(5个人的组合)的价格相加如果小于n存起来(包括分数)，再从所得出的集合中算出分数和最大的，不知道我的思路如何 } } } } }

Answer 5

/*
NBA球员有两个属性,身价,所得的分数,现在以n元钱在500个球员中购买5个球员,
要求,5个球员的分数最大,而且身价总和<n
*/
for($i = 0; $i < 500; $i++){ for($j = 0; $j < $i; $j++){

for($k = 0; $k < $j; $k++){

for($l = 0; $l < $k; $l++){

for($m = 0; $m < $l; $m++){

//假设球员有ID，那么三层循环中的$i、$j、$k皆为球员的ID，(买几位就有几个循环)如此能够保证所有的组合出现，将所有组合(5个人的组合)的价格相加如果小于n存起来(包括分数)，再从所得出的集合中算出分数和最大的，不知道我的思路如何 } } } } }

Answer 6

kyzy_yy_pm的逻辑好像可以，但是不是优化的算法

Answer 7

非常典型的01背包问题阿， 可以google "背包问题九讲"

http://hi.bccn.net/space-339919-do-blog-id-14722.html

Answer 8

写了个效率极差的，递归方案/********预设值********/
$totalPlayer = 20;//总可选球员数
$buyNum = 3;//准备买球员数
$totalMoney = 200;//预备了多少钱/********定义变量********/
$player = array();//可选人的属性数组
$currentBuyer = array();//当前买了哪些球员 1表示买 0 表示没买 和 $player对应
$currentScore = 0;//当前最佳购买方式，总分数
$currentValue = 0;//当前最佳购买方式，总花费
$count = 0;//因为算法效率极差，加个参数统计下，递归次数，哈哈
for($i=0;$i<$totalPlayer;$i++)
{
//初始化球员属性，价值 分数 是否被买下？
$player[$i] =array('value' => rand(10, 30), 'score' => rand(20, 50), 'buy' => 0);
}buyPlayer(0, 0, 0, 0);//选择球员
print_r($player);
print_r($currentBuyer);
echo $count;
/**
 * 选择球员
 *
 * @param   int         $i 球员编码，即$player下标
 * @param   int         $v 购买$i之前的球员的花费
 * @param   int         $s 购买$i之前的球员的总价值
 * @param   int         $p 购买$i之前的球员总数
 * @access  public
 * @return  void
 */
function buyPlayer($i = 0, $v = 0, $s = 0, $p = 0)
{
global $buyNum, $totalMoney, $player, $totalPlayer, $currentBuyer, $currentScore, $currentValue, $count; //递归+1了，哎，这效率
$count++;
//还有备选人员的情况
if($i < $totalPlayer)
{
//$i及后面的球员，先设定为不买
for($j=$i;$j<$totalPlayer;$j++)
{
$player[$j]['buy'] = 0;
}
//当球员没有买够
if($buyNum > $p)
{
//如果钱还能买下$i
if($player[$i]['value'] + $v <= $totalMoney)
{
$player[$i]['buy'] = 1;
buyPlayer($i+1, $player[$i]['value'] + $v, $player[$i]['score'] + $s, $p + 1);
}
//但是，我也可以不买
$player[$i]['buy'] = 0;
buyPlayer($i+1, $v, $s, $p);
}
//现在买够了
else
{
buyPlayer($totalPlayer, $v, $s, $p);
}
}
//没有备选人员了，直接比对结果
else
{
//有买更大价值的方案
if($currentScore < $s)
{
for($j=0;$j<$totalPlayer;$j++)
{
$currentBuyer[$j] = $player[$j]['buy'];
}
$currentScore = $s;
$currentValue = $v;
}
//同样的价值，如果有更省钱的方案的话
else if($currentScore == $s)
{
if($v < $currentValue)
{
for($j=0;$j<$totalPlayer;$j++)
{
$currentBuyer[$j] = $player[$j]['buy'];
}
}
}
}
}

Answer 9

buyPlayer可以把每次的计算结果缓存起来，避免重复计算

Answer 10

先对500人排序
找出最接近(n-1)/5 的5个人
(sorry,只有文字描述,没有代码)

Answer 11

我觉得可以让球员类 实现一个排序的接口
再写一个取集合的子集的方法来。
然后就可以先把这200个球员进行排序
然后再循环去200个球员中的子集
找到符合条件的就break

Answer 12

//1、排序球员的身价（为了得到最低身价球员的范围）
//2、循环判断最低价格的4为球员+循环中得到的某个(球员x)球员(假设ID为x)的身价相+后>=n(然后得到了最低身价的球员到x-1球员的ID)
//4、如此可以计算这些人中最大的四个数(分数)/*
以上我想了下效率高的很，但是不知道算法上的可能性如何
*/

Answer 13

*
NBA球员有两个属性,身价,所得的分数,现在以n元钱在500个球员中购买5个球员,
要求,5个球员的分数最大,而且身价总和<n
//1、排序球员的身价（为了得到最低身价球员的范围）
//2、循环判断最低价格的4为球员+循环中得到的某个(球员x)球员(假设ID为x)的身价相+后>=n(然后得到了最低身价的球员到x-1球员的ID)
//4、如此可以计算这些人中最大的五个数(分数)以下结果没有验证
*/$arr = array(
array('sj' => 100, 'fs' => '789'), 
array('sj' => 132, 'fs' => '456'), 
array('sj' => 652, 'fs' => '123'), 
array('sj' => 103, 'fs' => '987'), 
array('sj' => 145, 'fs' => '654'), 
array('sj' => 450, 'fs' => '321'), 
array('sj' => 170, 'fs' => '741'), 
array('sj' => 110, 'fs' => '852'), 
array('sj' => 155, 'fs' => '963'), 
array('sj' => 987, 'fs' => '369'), 
array('sj' => 456, 'fs' => '258'), 
array('sj' => 258, 'fs' => '147'), 
array('sj' => 321, 'fs' => '753'), 
array('sj' => 123, 'fs' => '357'), 
array('sj' => 741, 'fs' => '951'), 
array('sj' => 147, 'fs' => '159'), 
array('sj' => 963, 'fs' => '125'), 
array('sj' => 369, 'fs' => '521'), 
array('sj' => 357, 'fs' => '786')
);$num = count($arr);
$value = null;for($i = 0; $i < $num; $i++){
for($j = 0; $j < $i; $j++){
if($arr[$j]['sj'] > $arr[$i]['sj']){
$value = $arr[$j]['sj'];
$arr[$j]['sj'] = $arr[$i]['sj'];
$arr[$i]['sj'] = $value;
}
}
}$n = 1000;
$id = 0;
$money = 0;for($i = 0; $i < $num; $i++){
if($i < 4)$money += $arr[$i]['sj'];
else{
if($money + $arr[$i]['sj'] >= $n){
$id = $i - 1;
break;
}
}
}$arr_id = array();for($i = $id; $i >= 0; $i--){
if($i <= $id - 4)break;
$arr_id[] = $i;
}echo '<pre>';print_r($arr_id);

Answer 14

经测试，貌似正确
/*
NBA球员有两个属性,身价,所得的分数,现在以n元钱在500个球员中购买5个球员,
要求,5个球员的分数最大,而且身价总和<n
//1、排序球员的身价（为了得到最低身价球员的范围）
//2、循环判断最低价格的4为球员+循环中得到的某个(球员x)球员(假设ID为x)的身价相+后>=n(然后得到了最低身价的球员到x-1球员的ID)
//4、如此可以计算这些人中最大的五个数(分数)以下结果没有验证
*/$arr = array(
array('sj' => 100, 'fs' => '789'), 
array('sj' => 132, 'fs' => '456'), 
array('sj' => 652, 'fs' => '123'), 
array('sj' => 103, 'fs' => '987'), 
array('sj' => 145, 'fs' => '654'), 
array('sj' => 450, 'fs' => '321'), 
array('sj' => 170, 'fs' => '741'), 
array('sj' => 110, 'fs' => '852'), 
array('sj' => 155, 'fs' => '963'), 
array('sj' => 987, 'fs' => '369'), 
array('sj' => 456, 'fs' => '258'), 
array('sj' => 258, 'fs' => '147'), 
array('sj' => 321, 'fs' => '753'), 
array('sj' => 123, 'fs' => '357'), 
array('sj' => 741, 'fs' => '951'), 
array('sj' => 147, 'fs' => '159'), 
array('sj' => 963, 'fs' => '125'), 
array('sj' => 369, 'fs' => '521'), 
array('sj' => 357, 'fs' => '786')
);$num = count($arr);
$value = null;for($i = 0; $i < $num; $i++){
for($j = 0; $j < $i; $j++){
if($arr[$j]['sj'] > $arr[$i]['sj']){
$value = $arr[$j]['sj'];
$arr[$j]['sj'] = $arr[$i]['sj'];
$arr[$i]['sj'] = $value;
}
}
}$n = 1000;
$id = 0;
$money = 0;for($i = 0; $i < $num; $i++){
if($i < 4)$money += $arr[$i]['sj'];
else{
if($money + $arr[$i]['sj'] >= $n){
$id = $i;
break;
}
}
}$arr_id = array();
$money = 9999999;while($money > $n){
$money = 0;
$id--;
for($i = $id; $i > $id - 5; $i--){
$money += $arr[$i]['sj'];
}
}$arr_qy = array();for($i = $id; $i > $id -5; $i--){
$arr_qy[$i]['sj'] = $arr[$i]['sj'];
$arr_qy[$i]['fs'] = $arr[$i]['fs'];
}echo '<pre>';print_r($arr_qy);

Answer 15

楼上定义的变量好多 可不可以这样
建立 $score/$price数组 排序数组 得到最大性价比颗粒单位 $money2score 得到泛型数组
<SUN(MAX) $money2score>$score 索引还是保留原数组的 便于最后锁定编号
二分查找最接近$money2score/5的锚点 弹出数组 再递归找到下一个锚点 中间定义一个变量保留改变后的$money2score-$score[锚点]
因为是预先定义了MAX $money2score的值 所以不可能出现超支的情况 得到5个二分查找的锚点索引 
就是结果  当然了 可能会有重复 就看定义最近锚点的算发了 

Answer 16

大家测试下这个，写出来前后大约1个多小时，主要是每个地方都要仔细论证。
我这里测试没什么问题，我测试时只用了10个数据，主要是好将计算结果拿出来人为对比，数据太多了，没法人为对比。
速度是相当快的，即使是更多的球员或更多的个数也会很快。不同数目都测试过了。
/*注释部分是测试时生成数据用的，没什么用。没注释的才是正式代码。
汗一个，没学过什么算法，比较感兴趣，不过我还得继续加班，阿门！！<?php
$Data=array();
$N = (float)800;
$M = (float)5;
$avg = $N/$M;
$ResultData = array();
/*
//算出身价和分数的比率，及身价，和总价格/购买人数的平均价格
for($i=0;$i<10;$i++){
$t['money'] = mt_rand(10,19)*10;
$t['fen'] = mt_rand(80,90);
$Data[]=$t;
}
$cachedb="<?php\r\n";
$cachedb.='$Data='.vvar_export($Data).";\r\n";
$cachedb.="?>";
writeover("./data.php",$cachedb);
*/
require("data.php");//计算比率
foreach($Data as $key=>$item){
$item['m_f'] = (float)$item['money']/(float)$item['fen'];
$item['m_a'] = (float)$item['money']/(float)$avg;
$Data[$key]=$item;
}$formatData=array();
foreach($Data as $key=>$item){
//这里再加上$key为索引以防止身价和分数一样的部分球员，关键的也在这里
//还好php可以这样设置数组的key,其他语言可能就要单独计算一次了
$formatData[($item["m_f"]+$item["m_a"])."_$key"]=$item;
}
ksort($formatData);//按key排序//为了便于后面的计算按顺序将数组的key顺序变为数字
$i=0;
foreach($formatData as $key=>$item){
$formatData[$i]=$item;
$i++;
unset($formatData[$key]);//销毁原来的
}
//取出符合条件的序列
$z=0;
while(true){
$minIndex = NULL;//ResultData里最小分数的元素索引
$minFen = -1;//ResultData里最小的分数,用于求得最小分数元素的索引
$isBreak=true;
$N_tmp = 0;//临时计算总价的变量 for($i=$z;$i<($z+$M);$i++){
$ResultData[$i-$z]=$formatData[$i];//始终保持$M个元素
$N_tmp += $formatData[$i]['money'];
if($minFen==-1){
$minFen = $formatData[$i]['fen'];
$minIndex = $i-$z;
}else{
$minFen = min($minFen,$formatData[$i]['fen']);
$minIndex = $minFen==$formatData[$i]['fen'] ? $i-$z : $minIndex;
}
if($N_tmp>$N){
//跳出for循环，$z自增，进行下个序列的取值
$z++;
$isBreak=false;
break;
}
}
if($isBreak)break;//跳出while
}
//最后一步，循环将更优加入数组，并删除分数最小的球员
foreach($formatData as $key=>$fitem){
if(!in_array($fitem,$ResultData)){//不对比已经存在或身价分数完全一样的球员
//要注意一下这里的if
if($ResultData[$minIndex]['fen']<$fitem['fen']){
$countMoney = $fitem['money'];
foreach($ResultData as $key=>$ritem){
if($key!=$minIndex)$countMoney+=$ritem['money'];
}
if($countMoney<$N){
$ResultData[$minIndex] = $fitem;
$minFen = -1;
//再次求出最小分数的元素索引
foreach($ResultData as $key=>$ritem){
if($minFen==-1){
$minFen = $ritem['fen'];
$minIndex = $key;
}else{
$minFen = min($minFen,$ritem['fen']);
$minIndex = $minFen==$ritem['fen'] ? $key : $minIndex;
}
}
}
}else if($ResultData[$minIndex]['fen']==$fitem['fen'] && $ResultData[$minIndex]['money']>$fitem['money']){
$ResultData[$minIndex] = $fitem;
}
}
}print_r($ResultData);
/*
function vvar_export($array,$c=1,$t='',$var=''){
$c && $var="array(\r\n";
$t.="  ";
if(is_array($array)){
foreach($array as $key => $value){
$var.="$t\"".addslashes($key)."\"=>";
if(is_array($value)){
$var.="array(\r\n";
$var=vvar_export($value,0,$t,$var);
$var.="$t),\r\n";
} else{
$value=addslashes($value);
$value=str_replace("\'","'",$value);
$var.="\"".($value)."\",\r\n";
}
}
}
if($c){
$var.=")";
}
return $var;
}
function writeover($filename,$data,$method="rb+",$iflock=1,$check=1,$chmod=1){
$check && strpos($filename,'..')!==false && exit('Forbidden');
touch($filename);
$handle = fopen($filename,$method);
$iflock && flock($handle,LOCK_EX);
fwrite($handle,$data);
$method=="rb+" && ftruncate($handle,strlen($data));
fclose($handle);
$chmod && @chmod($filename,0777);
}
*/
?>

Answer 17

我感觉好像能把你的算法理解了，学到了不少东西。不过，算法有些缺陷。还需要优化如果我没理解错误，再找出一组符合要求的解以后逐一对不存在解里的元素，是否能让结果更优，作出判断。。但是问题就在这里，不一定替换一个结果就能更优，完全可以做到，替换了2个及以上的球员，才能更优。为此，我人工造一个数组，你不妨测试看看。
$N = (float)50;//足够买2球员
$M = (float)2;
$avg = $N/$M;
$ResultData = array();$Data = array(
array('money' => 25, 'fen' => 33),
array('money' => 37, 'fen' => 57),
array('money' => 14, 'fen' => 22),
array('money' => 11, 'fen' => 12),
);//程序找出了  14 => 22  25 => 33

Answer 18

再改了一次：<?php
$Data=array();
$N = (float)800;
$M = (float)5;
$avgm = $N/$M;
$avgf = -1;
$ResultData = array();for($i=0;$i<500;$i++){
$t['money'] = mt_rand(100,190);
$t['fen'] = mt_rand(1,500);
$Data[]=$t;
}
/*
$Data    = array(
    array('money' => 25, 'fen' => 33),
    array('money' => 37, 'fen' => 57),
    array('money' => 14, 'fen' => 22),
    array('money' => 11, 'fen' => 12),
);
*/
//require("./data.php");
//平均分
$Data_countFen = 0;
foreach($Data as $key=>$item){
$Data_countFen+=$item['fen'];
}
$avgf = (float)$Data_countFen/(float)count($Data);
//计算比率
foreach($Data as $key=>$item){
$item['m_am'] = (float)$item['money']/(float)$avgm;
$item['f_af'] = (float)$item['fen']/(float)$avgf;
$Data[$key]=$item;
}$formatData=array();
foreach($Data as $key=>$item){
//这里再加上$key为索引以防止身价和分数一样的部分球员，关键的也在这里
//还好php可以这样设置数组的key,其他语言可能就要单独计算一次了
$formatData[($item["m_am"]+$item["f_af"])."_$key"]=$item;
}
krsort($formatData);//按key排序
//为了便于后面的计算按顺序将数组的key顺序变为数字
$i=0;
foreach($formatData as $key=>$item){
$formatData[$i]=$item;
$i++;
unset($formatData[$key]);//销毁原来的
}
//取出符合条件的序列
$z=0;
while(true){
$countFen = 0;//ResultData的总分
$countMoney = 0;//ResultData的总价
$minIndex = NULL;//ResultData里最小分数的元素索引
$minFen = -1;//ResultData里最小的分数,用于求得最小分数元素的索引
$ResultData_Keys = array();//保存在ResultData里的元素在formatData里的索引
$isBreak=true; for($i=$z;$i<($z+$M);$i++){
$ResultData[$i-$z]=$formatData[$i];//始终保持$M个元素
$ResultData_Keys[$i-$z] = $i;
$countMoney += $formatData[$i]['money'];
$countFen += $formatData[$i]['fen'];
if($minFen==-1){
$minFen = $formatData[$i]['fen'];
$minIndex = $i-$z;
}else{
$minFen = min($minFen,$formatData[$i]['fen']);
$minIndex = $minFen==$formatData[$i]['fen'] ? $i-$z : $minIndex;
}
if($countMoney>$N){
//跳出for循环，$z自增，进行下个序列的取值
$z++;
$isBreak=false;
break;
}
}
if($isBreak)break;//跳出while
}
//最后一步，循环将更优加入数组，并删除分数最小的球员
foreach($formatData as $key=>$fitem){
if(!in_array($key,$ResultData_Keys)){//不对比已经存在的球员
//要注意一下这里的if
if($ResultData[$minIndex]['fen']<$fitem['fen']){
$thisCountMoney = $fitem['money'];
foreach($ResultData as $rkey=>$ritem){
if($rkey!=$minIndex)$thisCountMoney+=$ritem['money'];
}
if($thisCountMoney<$N){
$ResultData[$minIndex] = $fitem;
$minFen = -1;
//再次求出最小分数的元素索引
foreach($ResultData as $key=>$ritem){
if($minFen==-1){
$minFen = $ritem['fen'];
$minIndex = $key;
}else{
$minFen = min($minFen,$ritem['fen']);
$minIndex = $minFen==$ritem['fen'] ? $key : $minIndex;
}
}
}else{//ResultData_tmp进行符合条件的球员组合，并对比ResultData的总分
$ResultData_tmp=array();//临时对比结果数组
$ResultData_tmp[0]=$fitem;
//=========================================
$z=$key+1;//设定起始位置，因为前面的都是验证过的
while(true){
$countFen_tmp = $fitem['fen'];//ResultData_tmp的总分
$countMoney_tmp = $fitem['money'];//ResultData_tmp的总价
$minIndex_tmp = NULL;//ResultData_tmp里最小分数的元素索引
$minFen_tmp = -1;//ResultData_tmp里最小的分数,用于求得最小分数元素的索引
$ResultData_Keys_tmp =array();
$isBreak=true; for($i=$z;$i<($z+$M-1);$i++){
$ResultData_tmp[$i-$z+1]=$formatData[$i];//始终保持$M个元素
$ResultData_Keys_tmp[$i-$z+1] = $i;
$countMoney_tmp += $formatData[$i]['money'];
$countFen_tmp += $formatData[$i]['fen'];
if($minFen_tmp==-1){
$minFen_tmp = $formatData[$i]['fen'];
$minIndex_tmp = $i-$z+1;
}else{
$minFen_tmp = min($minFen_tmp,$formatData[$i]['fen']);
$minIndex_tmp = $minFen_tmp==$formatData[$i]['fen'] ? $i-$z+1 : $minIndex_tmp;
}
if($countMoney_tmp>$N){
//跳出for循环，$z自增，进行下个序列的取值
$z++;
$isBreak=false;
break;
}
}
if($isBreak)break;//跳出while
}
//序列取出完成，并对比ResultData的总分和ResultData_tmp的总分的大小
if($countFen_tmp>$countFen || ($countFen_tmp==$countFen && $countMoney_tmp<$countMoney)){
$ResultData = $ResultData_tmp;
$ResultData_Keys = $ResultData_Keys_tmp;
$countFen = $countFen_tmp;
$countMoney = $countMoney_tmp;
$minIndex = $minIndex_tmp;
$minFen = $minFen_tmp;
}
//=========================================
}
}else if($ResultData[$minIndex]['fen']==$fitem['fen'] && $ResultData[$minIndex]['money']>$fitem['money']){
$ResultData[$minIndex] = $fitem;
}
}
}print_r($ResultData);
?>

Answer 19

TO:dingsongtao/*
*
*
*用这个数据测试，还是有问题
*加循环深度的话，算法复杂度就会上来了
*而且循环层数，跟选取人数有关。2层可能只能解决选3个人的问题
*我觉得你程序前面部分想法挺有意思
*
*//*B*///程序运行结果
/*C*///应该是最优解$Data=array();
$N = (float)100;
$M = (float)4;
$avgm = $N/$M;
$avgf = -1;
$ResultData = array();$Data    = array(
    array('money' => 25, 'fen' => 33),/*B*/
    array('money' => 37, 'fen' => 57),/*B*//*C*/
    array('money' => 14, 'fen' => 22),/*B*//*C*/
    array('money' => 11, 'fen' => 12),/*C*/
    array('money' => 25, 'fen' => 33),
    array('money' => 37, 'fen' => 57),/*C*/
    array('money' => 14, 'fen' => 22),/*B*/
    array('money' => 11, 'fen' => 12),
);

Answer 20

1、csdn有专门的“计算方法”板块，当然实现时不一定就是你需要的语言版本
2、讨论具体的算法一定需要有明确的目的性，并且也只能得到一个子集
3、我不太明确楼主的需求，按描述只是一个抽象的数学命题。而公式推导并不是计算机的强项
4、满足 身价总和<n 的组合可以有若干组，而 满足 5个球员的分数最大 的条件不足，至少是范围不明确
如果是 身价总和n相同 且 5个球员的分数最大 的话，楼上几位给出代码的同仁在代码中都没有表现出来

Answer 21

<?php
    /*NBA球员有两个属性,身价,所得的分数,现在以v元钱在500个球员中购买5个球员,
    要求,5个球员的分数最大,而且身价总和最大*/    
    //初始化
    $data=array(
        array("price"=>4,"fs"=>5),
        array("price"=>5,"fs"=>6),
        array("price"=>6,"fs"=>7),
        array("price"=>7,"fs"=>8),
        array("price"=>8,"fs"=>9),
        array("price"=>9,"fs"=>10),
        array("price"=>10,"fs"=>11),
        array("price"=>11,"fs"=>12),
        array("price"=>12,"fs"=>13),
        array("price"=>13,"fs"=>14),
    );
    
    
    
    $n=count($data);//人数
    $m=50;//钱
    $q=3; //人数限制
    
    $c=array();
    $r=array();//记录=5的ij
    
    for($i=0;$i<$n+1;$i++){
        for($j=0;$j<$m+1;$j++){
            for($k=0;$k<$q+1;$k++){
               $c[$i][$j][$k]=array(); 
            }
        }
    }    for($i=1;$i<$n+1;$i++){
        for($j=1;$j<$m+1;$j++){
            for($k=1;$k<$q+1;$k++){ 
                if($data[$i][fs]<=$j&&(getFs(array_merge($c[$i-1][$j-$data[$i][price]][$k-1],array($data[$i])))>getFs($c[$i-1][$j][$k]))){ /*如果当前球员的价钱小于订购人员的钱,而且这次的方案比上一个方案好,那么就购买*/
                    $c[$i][$j][$k]= array_merge($c[$i-1][$j-$data[$i][price]][$k-1],array($data[$i])); //
                }else{
                    $c[$i][$j][$k]=$c[$i-1][$j][$k];//没有购买这个球员的时候,订购的钱,等于上一个人员的钱
                }
            }
        }
    }
    
    function getFs($arr,$num=false){
        $total=0;
        if(is_array($arr))foreach($arr as $item){
            if($num){
                 $total++;  
            }else{
               $total+=$item[fs];  
            }
        }
        return $total;
    }
    
    print_r($c[$n][$m][$q]);//只包含五位的,人员
?>我按照动态规划算法,搞出的,多出一维,大家帮我测试下,如果有错的话,告知,谢谢了

Answer 22

    $m=20;//钱
    $q=3; //人数限制
//其实还能凑出更多总分数的Array
(
    [0] => Array
        (
            [price] => 5
            [fs] => 6
        )    [1] => Array
        (
            [price] => 6
            [fs] => 7
        )    [2] => Array
        (
            [price] => 8
            [fs] => 9
        ))

Answer 23

    //初始化
     $data=array(
        array(),
        array("price"=>4,"fs"=>5),
        array("price"=>5,"fs"=>6),
        array("price"=>6,"fs"=>7),
        array("price"=>7,"fs"=>8),
        array("price"=>8,"fs"=>9),
        array("price"=>9,"fs"=>10),
        array("price"=>10,"fs"=>11),
        array("price"=>11,"fs"=>12),
        array("price"=>12,"fs"=>13),
        array("price"=>13,"fs"=>14),
    );
 $m=20;//钱
    $q=3; //人数限制
//结果Array
(
    [0] => Array
        (
            [price] => 5
            [fs] => 6
        )    [1] => Array
        (
            [price] => 7
            [fs] => 8
        )    [2] => Array
        (
            [price] => 8
            [fs] => 9
        ))还能找到更好的?

Answer 24

/* 我复制你的代码，你后来有改动么 *//* 初始化的值，我改了。代码出来结果不对 */
    $data=array(
        array("price"=>4,"fs"=>15),
        array("price"=>5,"fs"=>6),
        array("price"=>6,"fs"=>37),
        array("price"=>7,"fs"=>18),
        array("price"=>8,"fs"=>29),
        array("price"=>9,"fs"=>15),
        array("price"=>10,"fs"=>21),
        array("price"=>11,"fs"=>19),
        array("price"=>12,"fs"=>23),
        array("price"=>13,"fs"=>24),
    );
    
    
    
    $n=count($data);//人数
    $m=25;//钱
    $q=3; //人数限制

Answer 25

data的第一值,必须为空,我程序是从1开始的,造成第一条没用. 
$data=array(
array(),
        array("price"=>4,"fs"=>15),
        array("price"=>5,"fs"=>6),
        array("price"=>6,"fs"=>37),
        array("price"=>7,"fs"=>18),
        array("price"=>8,"fs"=>29),
        array("price"=>9,"fs"=>15),
        array("price"=>10,"fs"=>21),
        array("price"=>11,"fs"=>19),
        array("price"=>12,"fs"=>23),
        array("price"=>13,"fs"=>24),
    );

Answer 26

我的确是改了一点代码,下面的就是$data[$i][price]<=$j.<?php
    /*NBA球员有两个属性,身价,所得的分数,现在以v元钱在500个球员中购买5个球员,
    要求,5个球员的分数最大,而且身价总和最大*/
    //初始化
  $data=array(
  array(),
   array("price"=>4,"fs"=>15),
    array("price"=>5,"fs"=>6),
    array("price"=>6,"fs"=>37),
    array("price"=>7,"fs"=>18),
    array("price"=>8,"fs"=>29),
    array("price"=>9,"fs"=>15),
    array("price"=>10,"fs"=>21),
    array("price"=>11,"fs"=>19),
    array("price"=>12,"fs"=>23),
    array("price"=>13,"fs"=>24),  );    $n=count($data);//人数
    $m=20;//钱
    $q=3; //人数限制    $c=array();
    $r=array();//记录=5的ij    for($i=0;$i<$n+1;$i++){
        for($j=0;$j<$m+1;$j++){
            for($k=0;$k<$q+1;$k++){
                $c[$i][$j][$k]=array(); 
            }
        }
    }    for($i=1;$i<$n+1;$i++){
        for($j=1;$j<$m+1;$j++){
            for($k=1;$k<$q+1;$k++){                 if($data[$i][price]<=$j&&(getFs(array_merge($c[$i-1][$j-$data[$i][price]][$k-1],array($data[$i])))>getFs($c[$i-1][$j][$k]))){ 
                    /*如果当前球员的价钱小于订购人员的钱,而且这次的方案比上一个方案好,那么就购买*/
                    $c[$i][$j][$k]= array_merge($c[$i-1][$j-$data[$i][price]][$k-1],array($data[$i])); //
                }else{
                    $c[$i][$j][$k]=$c[$i-1][$j][$k];//没有购买这个球员的时候,订购的钱,等于上一个人员的钱
                }
            }
        }
    }    function getFs($arr,$num=false){
        $total=0;
        if(is_array($arr))foreach($arr as $item){
                if($num){
                    $total++;  
                }else{
                    $total+=$item[fs];  
                }
        }
        return $total;
    }    //print_r($c);      
    print_r($c[$n][$m][$q]);//只包含五位的,人员
?>

Answer 27

我认为可以套用类似于求数组中K个最大值的方法。先建一个大小为5的最小堆（按球员的得分建立，且保证这5个球员的身价和小于n），一次扫描之后的元素，如果得分大于堆顶且加入之后的堆中元素的身价和小于等于n，否则不加入，一直扫描，直到最后一个元素为止。
轻拍~