时间:2021-07-01 10:21:17 帮助过:4人阅读
29,
'b' => 11,
'c' => 33,
'd' => 84,
'e' => 46,
'f' => 67,
'g' => 19,
'h' => 18,
'i' => 88,
'j' => 8,
'k' => 54,
'l' => 86,
'm' => 88,
'n' => 29,
'o' => 96,
'p' => 1,
'q' => 4,
'r' => 100,
's' => 89,
't' => 44,
'u' => 53,
'v' => 68,
'w' => 12,
'x' => 54,
'y' => 23,
'z' => 78,
);
?>
其中$data包含100组数据,每组数据由字母组成,数量和内容都是随机的。
其中$times是每个字母出现的次数。
现在需要从$data中取20组数据,使这20组数据排重过滤后组成的新数据中,所有字母出现次数总和最小(相比于其他的可能的组合)。
穷举法比较的路子走不通,因为从100组数据中取所有20组数据可能的组合,这个数据量太大。
请问,应该如何获取?
遇到一个算法问题,一直不得求解,恳请大神指点!
现有数据:
29,
'b' => 11,
'c' => 33,
'd' => 84,
'e' => 46,
'f' => 67,
'g' => 19,
'h' => 18,
'i' => 88,
'j' => 8,
'k' => 54,
'l' => 86,
'm' => 88,
'n' => 29,
'o' => 96,
'p' => 1,
'q' => 4,
'r' => 100,
's' => 89,
't' => 44,
'u' => 53,
'v' => 68,
'w' => 12,
'x' => 54,
'y' => 23,
'z' => 78,
);
?>
其中$data包含100组数据,每组数据由字母组成,数量和内容都是随机的。
其中$times是每个字母出现的次数。
现在需要从$data中取20组数据,使这20组数据排重过滤后组成的新数据中,所有字母出现次数总和最小(相比于其他的可能的组合)。
穷举法比较的路子走不通,因为从100组数据中取所有20组数据可能的组合,这个数据量太大。
请问,应该如何获取?
29,
'b' => 11,
'c' => 33,
'd' => 84,
'e' => 46,
'f' => 67,
'g' => 19,
'h' => 18,
'i' => 88,
'j' => 8,
'k' => 54,
'l' => 86,
'm' => 88,
'n' => 29,
'o' => 96,
'p' => 1,
'q' => 4,
'r' => 100,
's' => 89,
't' => 44,
'u' => 53,
'v' => 68,
'w' => 12,
'x' => 54,
'y' => 23,
'z' => 78,
);
/**
* 算法思路:
* 1.先排重
* 2.排重之后的操作见注释
*/
$newData = array();
foreach ($data as $oldKey => $item){
//去重后
$removeDuplicatedItem = array_unique($item,SORT_NATURAL);
$newData[$oldKey] = $removeDuplicatedItem;
}
uasort($newData,function($a,$b){
$countForA = count($a);
$countForB = count($b);
if ($countForA == $countForB){
return 0;
}
return ($countForA > $countForB ? 1 : -1);
});
$counter = 0;
$targetData = array();
foreach ($newData as $targetKey =>$newItem){
$targetData[$targetKey] = $newItem;
$counter++;
if($counter == 20){
break;
}
}
$endMemoryUsage = memory_get_usage();
$endTimeStamp = microtime(true);
$totalMemoryUsage = $endMemoryUsage - $startMemoryUsage;
$totalTimeStamp = $endTimeStamp - $startTimeStamp;
print_r($totalMemoryUsage);
echo "\n";
print_r($totalTimeStamp);
echo "\n";
print_r($targetData);