こちらではpaiza事務局側で作成した模範解答を掲載していす。
PHP: paiza事務局作成コード Vol.3 解説ブログ版
解説ブログ： もし先輩女子エンジニアが『アルゴリズム』を図解で教えてくれるとしたら
得点：100点
通過テストケース：7/7
<?php
fscanf(STDIN, '%d', $M); // 必要人数
fscanf(STDIN, '%d', $N); // 入力社数
// q 各下請け会社の人員数
// r 各下請け会社のへの発注費用
$min_cost = 0;
for($i = 0; $i < $N; $i++) {
fscanf(STDIN, '%d %d', $q[$i], $r[$i]);
$min_cost += $r[$i];
}
$dp = array();
$dp[0] = 0;
// $dp[人数]=最低価格
// 入力社数分ループ
for($i = 0; $i < $N; $i++){
$dp_tmp = $dp; // $dp_tmpは足しあげ処理結果を格納
// 人数ループ
foreach ($dp as $key => $value){
$total_q = $key + $q[$i]; // 入力済み人数に足しあげる
$total_r = $value + $r[$i];
if(!isset($dp_tmp[$total_q])){
// 該当人数に値が入力されていなかった場合
$dp[$total_q] = $total_r;
}else{
// 当該人数が入力済みの場合より小さい合計金額を入力
if($dp_tmp[$total_q] > $total_r){
$dp[$total_q] = $total_r;
}
}
//
if($total_q >= $M and $min_cost > $total_r){
$min_cost = $total_r;
}
}
}
print $min_cost;
PHP: paiza事務局作成コード Vol.2 動的計画法
得点：100点
通過テストケース：7/7
<?php
fscanf(STDIN, '%d', $M);
fscanf(STDIN, '%d', $N);
$QR = array();
$sum_q = 0;
$sum_r = 0;
for($i = 0; $i < $N; $i++) {
fscanf(STDIN, '%d %d', $QR[$i][0], $QR[$i][1]);
$sum_q += $QR[$i][0];
$sum_r += $QR[$i][1];
}
$m = $sum_q - $M;
$dp = array();
for($i = 0; $i < $m+1; $i++)$dp[$i] = 0;
for($i = 0; $i < $N; $i++) {
$q = $QR[$i][0];
$r = $QR[$i][1];
for($j = $m; $j >= $q; $j--) {
$dp[$j] = max($dp[$j], $dp[$j-$q]+$r);
}
}
print(($sum_r - $dp[$m])."\n");
PHP: paiza事務局作成コード Vol.1 O(2^n)
得点：71点
通過テストケース：5/7
<?php
fscanf(STDIN, '%d', $M);
fscanf(STDIN, '%d', $N);
$QR = array();
for($i = 0; $i < $N; $i++) {
fscanf(STDIN, '%d %d', $QR[$i][0], $QR[$i][1]);
}
$use_list = array();
for($i = 0; $i < pow(2, $N); $i++) {
$use_list[] = str_split(str_pad(decbin($i),$N,"0",STR_PAD_LEFT));
}
#使う使わないリストから、人月を満たせる組み合わせで最安を探す
$ans = 0;
foreach($QR as $v) {
$ans += $v[1];
}
foreach($use_list as $v) {
$cost = 0;
$ningetsu = 0;
foreach($v as $key => $vv) {
if($vv == 1) {
$ningetsu += $QR[$key][0];
$cost += $QR[$key][1];
}
}
if($ningetsu >= $M && $ans > $cost) {
$ans = $cost;
}
}
print($ans."\n");
