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

2022年8月17日

【DPメニュー】> FINAL問題【部分和】部分和問題 4 (paizaランク B 相当) [難易度: 1791 ±22]

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

問題文

1 ~ n の番号がついた n 種類のおもりがあり、おもり i の重さは a_i です。それぞれのおもりは無限個存在しており、任意のおもりを任意の個数使うことができます。

このとき、おもりを選んで重さの和を x となるようにすることができるかどうか判定してください。

入力値（例）
5 10
9
3
4
11
8

出力値（例）
yes

解答例

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

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

    echo ($dp[$x]) ? "yes" : "no";
?>

<?php

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

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

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

}

$dp[0] = true;

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

$dp[$i] = false;

}

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

for($j = $a[$i]; $j < $x+1; $j++){

if($dp[$j-$a[$i]]) {

$dp[$j] = true;

}

//print_r($dp);

echo ($dp[$x]) ? "yes" : "no";

解答例

カテゴリー