算法问题：从数据集中按规则取指定数量的数据集合

程序员文章站 2024-01-14 16:22:16

...

遇到一个算法问题，一直不得求解，恳请大神指点！
现有数据：

 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,
);
?>

 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);