【DPメニュー】部分和問題 3 (paizaランク B)-解答例-PHP編

2022年8月17日

【DPメニュー】> 【部分和】STEP: 3 部分和問題 3 (paizaランク B 相当) [難易度: 2080 ±12]

※リンク先へ移動するためには[paiza]へのログインが必要です。

問題文

1 ~ n の番号がついた n 個のおもりがあり、おもり i の重さは a_i です。

おもりを何個か選んで重さの和が x となるようにする方法を考えたとき、選ぶおもりの個数の最小値を出力してください。なお、同じおもりを2個以上選ぶことはできません。

なお、重さの和が x となるようにおもりを選ぶ方法が存在しない場合は-1と出力してください。

入力値（例）
5 10
7
3
4
3
2

出力値（例）
2

解答例

<?php
    list($n, $x) = explode(" ", trim(fgets(STDIN)));
    
    for ($i = 0; $i < $n; $i++) {
        $a[$i] = trim(fgets(STDIN));
    }

    $dp[0] = 0;
    
    for ($i = 1; $i <= $x; $i++) {
        $dp[$i] = $n+1;
    }
    
    for($i = 0; $i < $n; $i++){
        for($j = $x; $j >= $a[$i]; $j--){
            if($dp[$j-$a[$i]] == $n+1)   continue;
            $dp[$j] = min($dp[$j], $dp[$j-$a[$i]]+1);
        }
    }
    //print_r($dp);

    echo ($dp[$x] == $n+1) ? -1 : $dp[$x];
?>

<?php

list($n, $x) = explode(" ", trim(fgets(STDIN)));

for ($i = 0; $i < $n; $i++) {

$a[$i] = trim(fgets(STDIN));

}

$dp[0] = 0;

for ($i = 1; $i <= $x; $i++) {

$dp[$i] = $n+1;

}

for($i = 0; $i < $n; $i++){

for($j = $x; $j >= $a[$i]; $j--){

if($dp[$j-$a[$i]] == $n+1) continue;

$dp[$j] = min($dp[$j], $dp[$j-$a[$i]]+1);

}

//print_r($dp);

echo ($dp[$x] == $n+1) ? -1 : $dp[$x];

解説

1) 整数n、整数xを受け取ります。
2) 配列aを受け取ります。
3) 配列dp[i]にn+1を代入します。
4) i = 1～nで繰り返し設定をします。
5) 二重ループでj = x～a[i-1]で繰り返し処理を設定します。
6) dp[j]とdp[j-a[i-1]+1でおもりの少ない方で更新します。
7) dp[x]を返します。n+1個の場合は-1を返す。
コードの中で、n+1としているのは、おもりの個数はnなので、おもりをn+1個選ぶような状況は起こりえないためです。

解答例

解説

カテゴリー