投稿者: bgbgbg

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

動的計画法のコードをPHPで書いてみました
（Rubyのコードとロジックは同じです）

<?php
$M = trim(fgets(STDIN)); // 人員
$N = trim(fgets(STDIN)); // 会社数

$minCost = 0;
$num = array();
$cost = array();

for($i = 0; $i < $N; $i++) {
    fscanf(STDIN, '%d %d', $num[$i], $cost[$i]);
    $minCost += $cost[$i];
}

$dp[0] = 0;
for($n = 0; $n < $N; $n++) {
    foreach ($dp as $key => $value) {
        $totalNum = $key + $num[$n];
        $totalCost = $value + $cost[$n];
        if (isset($dp[$totalNum]) == false) {
            $dp[$totalNum] = $totalCost;
        } else {
            if ($dp[$totalNum] > $totalCost) {
                $dp[$totalNum] = $totalCost;
            }
        }
        if ($totalNum >= $M && $minCost > $totalCost) {
            $minCost = $totalCost;
        }
    }
}

//ksort($dp);
//var_dump($dp);
echo $minCost;

人数ごとの結果を残して、再利用しています（わかりにくい..）
一番低いコストの値だけを残しています
まだ無駄のあるコードで、改良の余地ありです

paizaでコードを提出すると採点してくれます
結果はこんな感じです
http://paiza.jp/poh/kirishima/result/fb88794dc2e25c011a242f318744ccc9

最速コードを目指したりするとまだ遊べるようです

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