4

以下を解決するための効率的なアルゴリズムのヒントが欲しいです: (わかりました、問題はそれではなく、簡単にするためにこれを作成しただけです)。
例: N 個の広告ボードのうち、 K個の連続するボードに会社のM個の広告があるはずです。また、広告は 、N=3、K=2、M=1 の場合に最小数の広告のみが使用されるように使用されます。答えは 010 です。 N=6、K=3、M=2 の場合、答えは 6 になります 。011011、011101、011110、101101、101110、110110。




私は、反復的かつ再帰的な方法ですべての組み合わせを（バイナリアプローチで）作成するアプローチを取りました。その後、フィルタリングしました。N が大きい場合はクラッシュします (予想どおり)。これらを解決する効率的な方法はありますか？

私は別のアプローチを取りましたが、うまくいきません.. :(

2 番目のアプローチ

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;

}
?>
4

1 に答える 1

1

私のコメントを詳しく説明するために、ここに1つの潜在的な解決策があります（ただし、より良い解決策がなければ非常に失望します）

1) 最初に、有効な解に必要な 1 の最小数を計算します。(これは単純だと思いますmax(M, floor(n/k)*m + max(0, n%k-(k-m)))。この式は、一度に 1 文字ずつ文字列を作成し、可能な限り 0 を配置することから導出されます)

2) ここで、N > K であると仮定します (そうでない場合、答えは自明です)。サブ問題を次のように定義します。

たとえば、文字列が "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 に答える