「もし先輩女子エンジニアが『アルゴリズム』を図解で教えてくれるとしたら」を解いてみた

paizaの
もし先輩女子エンジニアが『アルゴリズム』を図解で教えてくれるとしたら
という解説が公開されました

アルゴリズムのプログラムをあまりやったことがなかったの考えてみました
解説記事の全文探索をphpで書くとこんな感じ


<?php
function calc($cost, $staff, $idx) {
    global $n, $m, $result, $company;
    if ($n <= $idx) {
        return;
    }   
    if ($m <= $staff + $company[$idx]['num']) {
        $result[] = $cost + $company[$idx]['cost'];
    } else {
        calc($company[$idx]['cost'], $company[$idx]['num'], $idx + 1); 
    }
    calc($cost, $staff, $idx + 1);
}

$m = trim(fgets(STDIN)); // 人員
$n = trim(fgets(STDIN)); // 会社数

$company = array();
for ($i=0; $i < $n; $i++) {
    $t = trim(fgets(STDIN));
    $t = str_replace(
        array("\r\n", "\r", "\n"), '', $t
    );      
    $e = explode(" ", $t);
    $company[$i]['num'] = $e[0];
    $company[$i]['cost'] = $e[1];
}

$result = array();
calc(0, 0, 0);
arsort($result);
echo (array_shift($result));

これだと、会社数が増えたときに組み合わせが多すぎて、テストが通らないみたいです
ビットを使えば再帰関数が不要になります(記事参照)が、同じく全文探索です

計算結果を再利用する動的計画法を使えば、組み合わせが会社数×人数の組み合わせとなるので処理数が減らせテストがすべてクリアできたようです
(解答例 http://paiza.jp/poh/code_index はpaizaに会員登録するとみれます)

カテゴリーphp

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください