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

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に会員登録するとみれます）