4

I want a hint on a efficient algorithm of solving the following: (Okay, The question was not that, I just made this for simplicity).
Example: Out of N Advert boards there should be M advert of a company in K consecutive boards. and the Adverts will be used such a way that only MINIMUM number of Adverts will be used
if N=3,K=2,M=1. The answer will be one 010;
if N=6, K=3, M=2 the answer will be 6.
011011, 011101, 011110, 101101, 101110, 110110.

I took the approach of Creating all the combinations(with binary approach) with iterative and recursive method.After that I filtered it. It is working well except if N is big it will crash.(as expected). So Is there any efficient method of solving these?

I just took another approach but it is not going to well .. :(

Second approach

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

First Approach

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

}
?>
4

1 回答 1

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)) 时间内运行

于 2013-05-22T19:49:14.800 回答