php - 从 N 个项目中选择最少的项目，使得 K 个连续项目中应该有 M 个项目

Question

我想要一个解决以下问题的有效算法的提示:(好吧，问题不是那个，我只是为了简单起见而做的)。
示例:在 N 个广告板上，应该有 M 个公司的广告在 K 个连续的板上。并且广告的使用方式将仅使用 MINIMUM 数量的广告
如果 N=3，K=2，M=1。答案将是一个 010；
如果 N=6，K=3，M=2，答案就是 6。
011011,011101,011110,101101,101110,110110.

我采用了使用迭代和递归方法创建所有组合(使用二进制方法)的方法。之后我对其进行了过滤。它运行良好，除非 N 很大它会崩溃。(如预期的那样)。那么有什么有效的方法可以解决这些问题吗？

我只是采取了另一种方法，但效果并不好.. :(

第二种方法

if($n%$k == 0){
$perm = $m*($n/$k);
}else{
$perm = $m*ceil($n/$k);
}
Then I will do the nCr... and now I'm lost

第一种方法

<?php
$n = $input1;$k = $input2;$l=$input3; $total = 0;
$flag = false;$arrays = array();$z=0;$min=$n;$x=0;

$total_permutations = pow(2,$n);
for($i=0;$i<$total_permutations;$i++){
    $binary = base_convert($i, 10, 2);
    $binary = str_pad($binary, $n,"0", STR_PAD_LEFT);
        for($j=0;$j<=($n-$k);$j++){
            $flag = false;$x=0;
                for($m=0;$m<$k;$m++){
                    $x += intval($binary{$j+$m});
                }
            if($x<$l){
                $flag = true;
                break;
            }
        }
    if(!$flag){
        $arrays[$z]=str_split($binary);
        $arrays[$z] = array_map('intval', $arrays[$z]);
        $z++;
    echo $binary."<br />";
    }
    unset($binary);
}
$min = min(array_map('array_sum',$arrays));
echo "------------<br />";
foreach($arrays as $val){
    $sum = array_sum($val);
    if($sum == $min){
        echo implode("",$val);echo "<br>";
        $total++;
    }
}
return $total;

}
?>

Answer 1

为了详细说明我的评论，这里有一个可能的解决方案(不过，如果没有更好的解决方案，我会非常失望)

1) 首先，计算有效解中所需的最小 1 数。 (我相信这很简单 max(M, floor(n/k)*m + max(0, n%k-(k-m)))。该公式源自构建一个字符串一个字母一次，尽可能放置 0)

2) 现在，假设 N > K(否则答案是微不足道的)。我们将子问题定义为:“给定长度为 K 的前缀 P 和要放置的预算 B 1，有多少种方法可以填充 N 个字符同时仍然执行 M 规则？”

例如，假设我们的字符串是“101XXXXXX”，K = 3，M = 2，B = 4。这里，N = 6，P =“101”。我们这样解决这个子问题:

a) Check if the budget is big enough in O(N) time.  Return 0 if it isn't
   If N=0, return 1 trivially
b) Set total possible solutions to 0
c) Set the first unknown character to 1.  Compute the new prefix P'
   (by stripping off the first character, and adding a "1" to the end),
   the new B' = B-1, the new N' = N-1, and solve the new sub-problem:
     Add its result to our total
d) Set the unknown character to 0 instead:  But only if the new prefix P'  
  (strip, add "0") has at least M 1's.  If so, set B' = B-1, N' = N-1,  
  and solve the new sub-problem.  Add its result to our total
e) Return the total

要解决原始问题，只需考虑所有可能的前缀 P(其中的所有 nCr(K,M))，然后总结派生子问题的解决方案。通过将结果缓存到基于唯一输入 P、N 和 B 的子问题，我们大大减少了重复工作的数量。摊销分析应该表明完整的解决方案在 O(N*nCr(K,M)) 时间内运行