题目：用户上传若干个 adapter index 序列，这些序列是由 “A”、“T”、“C”、“G” 四种字母组成的字符串，长度可能是6、8、16。然后指定一个数字 n，需要输出 count 组的 adapter index 的组合，每组中必须有 n 个adapter index，且使这些组合中，每一位的四种字母占比要尽量均匀，而且都在 12.5%-60% 之间，优先满足前 count 个分组，最终不足 n 个或者不满足占比的要舍弃。如果最后输出这样一组 adapte indexr：
ACTGCAG
TGAAGCT
GCATTAG
GATGATG
那么第一位的 A 占比为 25%，T占比25%，G占比50%，C占比0%；第二位的 A 占比25%，T占比0%， G占比25%，C占比50%......依次计算。
由题目可知，我们最终想要的结果是一些字符串的分组，这个问题就非常类似动态规划里的背包问题或者是股票问题。
背包问题中，我们要找的是把物品放入限制容量的背包的最大价值，需要从从若干个物品中挑选，本问题也可以看成是从若干个字符串中挑选出最符合要求的（即 ATCG 最均匀的），所以对于单个分组，我们可以使用动态规划，来求得最佳的组合。问题中也提到，可以优先满足前几个组，之后不满足就可以舍弃，我们就可以使用递归，先满足第一组，然后再在剩下的 adapter 中继续挑选满足要求的最佳组合。
先来构建动态规划的框架。
动态规划中，我们第一步先要找出状态和选择。
在这个问题中，我们要做的是遍历所有的 adapter，然后判断把当前 adapter 加入到数组中时，是否为“最佳”的情况。
状态有两种：数组中 adapter 的数量、可选择的 adapter。
选择：当前的 adapter 是否进入数组。
找到状态和选择之后，动态规划的问题基本就可以解决了，有一个动态规划的框架：
for 状态1 in 状态1的所有取值
for 状态2 in 状态2的所有取值
for ...
dp[状态1][状态2][...] = 择优（选择1，选择2....）
第二步要明确 dp 数组的定义
dp 数组是什么？其实就是描述局部问题的一个数组，刚才提到的“状态”，现在就要用 dp 数组把状态表示出来。
我们的状态有两个，所以我们就需要一个二维数组，一维表示可选择的 adapter，一维表示当前数组中已有的 adapter 的数量。
dp[i][w]的定义如下：对于前 i 个adapter，当前数组中的 adapter 数量为 w，这种情况下当前数组的最优均匀程度为 dp[i][w]。
注：题目中的最优解，我们可以理解为最均匀，所以这里的最优情况即为最均匀程度。
如果 dp[3][5] = 6，其含义就是对于给定的所有 adapter ，如果只对前 3 个 adapter 进行选择，当数组中有 5 个adapter 时，最均匀程度就为 6。
设 adapter 总数为 N 个，数组的容量为 W。
根据这个定义，我们想求的最佳答案就是 dp[N][W]。
还要记得处理 base case，这个问题的 base case 就是 dp[0][..] 和 dp[..][0]，因为当没有可选 adapter 或者数组容量为 0 时，均匀程度无法计算。
如此，细化动态规划的框架：
for i in count(indexes):
for w in [1...8]
dp[i][w] = max(
把当前 index 放入结果集，
不把当前 index 放入结果集
)
return dp[count(indexes)][8];
根据“选择”，思考状态转移的逻辑
简单来说，就是上面的把“把当前 index 放入结果集” 和 “不把当前 index 放入结果集” 如何用代码体现呢？
前面提到，对于前 i 个adapter，当前数组中的 adapter 数量为 w，这种情况下当前数组的最优均匀程度为 dp[i][w]**。
如果没有把第 i 个 adapter 放入数组，那么最均匀程度 dp[i][w] 就应该等于 dp[i-1][w]，继承之前的结果。
如果把第 i 个 adapter 放入了数组，那么最均匀程度 dp[i][w] 就应该是在dp[i-1][w-1] 的基础上进行计算，当数组新添加了一个元素 ，就应该计算新元素加入之后的分值。
既然我们最后要输出的是一个数组，所以还需要一个数组来记录数组中的 adapter。
细化一下代码：
private function filtrateAdapters($indexes, $count)
{
// 初始化数组
$adapters = [];
$indexesLen = count($indexes);
// 放入第一个 index
$adapters[0][0] = [];
$percent[0][0] = -100000;
// 动态规划
for ($i = 0; $i <= $indexesLen; $i ++) {
for ($w = 0; $w <= $count; $w ++) {
// 初始化的一部分，分值初始化为0，数组初始化为空数组
if ($i == 0 || $w == 0) {
$percent[$i][$w] = 0;
$adapters[$i][$w] = [];
continue;
}
// 判断最优
// 放入的情况
$adapters[$i][$w] = array_merge($adapters[$i-1][$w-1], [$indexes[$i]]);
$baseBank = $this->baseRank($adapters[$i][$w]);
$percent[$i][$w] = $this->percentageScore($baseBank);
// 不放的情况
if ($percent[$i][$w] < $percent[$i-1][$w] && $percent[$i-1][$w] != 0) {
// 出栈
//dd($adapters[$i][$w], $adapters[$i-1][$w-1], $percent[$i][$w], $percent[$i-1][$w-1]);
$adapters[$i][$w] = $adapters[$i-1][$w];
$percent[$i][$w] = $percent[$i - 1][$w];
}
}
}
return $adapters[$indexesLen][$count];
}
这里我们需要一个计算“均匀程度”的方法，这里就不再贴出来了，就是简单地每一位计算一下。
然后我们需要用递归的方法来求出最终的若干个数组，整理出代码：
private function filtrateAdapters(&$indexes, $count, &$res=[])
{
// 初始化数组
$result = [];
$adapters = [];
$indexesLen = count($indexes);
$adapters[0][0] = [];
$percent[0][0] = -100000;
// 动态规划
for ($i = 0; $i <= $indexesLen; $i ++) {
for ($w = 0; $w <= $count; $w ++) {
// 初始化的一部分，分值初始化为0，数组初始化为空数组
if ($i == 0 || $w == 0) {
$percent[$i][$w] = 0;
$adapters[$i][$w] = [];
continue;
}
// 判断最优
// 放入的情况
$adapters[$i][$w] = array_merge($adapters[$i-1][$w-1], [$indexes[$i]]);
$baseBank = $this->baseRank($adapters[$i][$w]);
$percent[$i][$w] = $this->percentageScore($baseBank);
// 不放的情况
if ($percent[$i][$w] < $percent[$i-1][$w] && $percent[$i-1][$w] != 0) {
$adapters[$i][$w] = $adapters[$i - 1][$w];
$percent[$i][$w] = $percent[$i - 1][$w];
}
}
}
// 最后判断结果，如果是负值，代表结束
if (count($adapters[$indexesLen][$count]) < $count || $percent[$indexesLen][$count] < 0) {
//dd($res);
return $res;
}
// 判断是否超出界限
$baseBank = $this->repository->baseRank($adapters[$indexesLen][$count]);
foreach ($baseBank as $item) {
foreach ($item as $value) {
$p = str_replace("%", '', $value);
if ($p > 60 || $p < 12.5) {
return $res;
}
}
}
$res[] = [
'adapters' => $adapters[$indexesLen][$count],
'percent' => $this->repository->baseRank($adapters[$indexesLen][$count])
];
// 然后从原indexes数组中去除已选的元素，继续下一轮
$newIndexes = array_diff($indexes, $adapters[$indexesLen][$count]);
$this->filtrateAdapters($newIndexes, $count, $res);
}
// 根据占比来计算分值
private function percentageScore($baseBank)
{
// 如果超出界限，则返回-1，其他情况计算平均值
/**
* 结构：
* a=>[0:10%,1:10%...]
* t=>[0:10%,1:10%...]
* c=>[0:10%,1:10%...]
* g=>[0:10%,1:10%...]
*/
$score = 0;
foreach ($baseBank as $item) {
foreach ($item as $value) {
$p = str_replace("%", '', $value);
if ($p > 60 || $p < 12.5) {
$score += -1;
}
if ($p > 25) {
$score += (60-$p)/35 * 100;
} elseif ($p <= 25) {
$score += ($p-12.5)/12.5 * 100;
}
}
}
return $score;
}
网友评论