[Ruby]paiza DPメニュー部分和

2021-11-19

こんにちは！じゃいごテックのあつしです。

今回はpaiza DPメニュー 「セクション5【部分列】 STEP1, FINAL」 を解説します。
DPメニューは動的計画法(Dynamic Programming, DP)に関する6個のセクションで構成されています。

セクション6【部分和】は、n種類の重さのおもりの組み合わせと、指定された重さxについて調べる問題です。

STEP1： n種類, 各1個のおもりの組み合わせで重さxが作れるか
STEP2： n種類, 各1個のおもりの組み合わせで重さxになる組み合わせがいくつあるか
STEP3： n種類, 各1個のおもりの組み合わせで重さxになる組み合わせのうち、おもりの数の最小はいくつか
FINAL： n種類, 各無限個のおもりの組み合わせで重さxが作れるか

STEP問題を解いてみる
FINAL問題: 部分和問題 4 (paizaランク B 相当)
今回のまとめ

STEP問題を解いてみる

簡単な解説は付けていますが、難しいと感じたら下記の記事も参考にしてみて下さい。

分割統治法・動的計画法

[アルゴリズム(Ruby)]分割統治法・動的計画法

メソッドの定義と呼び出し

[Ruby]メソッドの定義と呼び出し

標準入力・標準出力

STEP1: 部分和問題 1 (paizaランク B 相当)

n種類, 各1個のおもりを組み合わせて重さxが作れるかを調べる問題です。

解答例

INPUT1 = <<~"EOS"
  5 19
  7
  18
  5
  4
  8
EOS
OUTPUT1 = <<~"EOS"
  yes
EOS

def solve(input_lines)
  # 入力受け取り
  input_lines = input_lines.split("\n")
  n, x = input_lines.shift.split.map(&:to_i)
  *a = input_lines.map(&:to_i)

  # dpテーブル初期化
  # おもりを選ばなければ重さの和を0とすることができる
  dp = [true] + [false] * x

  # dpテーブル更新
  1.upto(n) do |i|
    x.downto(a[i - 1]) do |j|
      # a[i-1] を使って j が作れるか
      dp[j] = true if dp[j - a[i - 1]]
    end
    break if dp[x]
  end

  # x が作れるかを出力
  dp[x] ? "yes" : "no"
end

puts solve(STDIN.read)

# 確認用コード
# puts solve(INPUT1)
# > yes

#        | j
#  i     | 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 |
#  - ( 0)| t, f, f, f, f, f, f, f, f, f, f, f, f, f, f, f, f, f, f, f |
# [1]( 7)| t, f, f, f, f, f, f, t, f, f, f, f, f, f, f, f, f, f, f, f |
# [2](18)| t, f, f, f, f, f, f, t, f, f, f, f, f, f, f, f, f, f, t, f |
# [3]( 5)| t, f, f, f, f, t, f, t, f, f, f, f, t, f, f, f, f, f, t, f |
# [4]( 4)| t, f, f, f, t, t, f, t, f, t, f, t, t, f, f, f, t, f, t, f |
# [5]( 8)| t, f, f, f, t, t, f, t, t, t, f, t, t, t, f, t, t, t, t, t |

整数n, 整数x, 配列aを受け取る。
dpに[true] + [false] * xを代入する。
(何も選ばなければ重さ0が作れる)
i = 1 ~ nで繰り返し処理を設定する。
- j = x ~ a[i - 1]で繰り返し処理を設定する。
  - dp[j] = true if dp[j - a[i - 1]]
    おもりa[i-1]を使って重さjが作れるならdp[j]をtrueで更新する
dp[x]がtrueならYes、falseならNoを返す

処理の流れ

スペースの都合上、以下の例で説明します。

おもりの種類 n = 4
作りたい重さ x = 9
各おもりの重さ a = [3, 2, 5, 6]

DP6-1-1

dp = [true] + [false] * x で初期化

おもりを選ばなければ重さ0が作れる

ここからi = 1 ~ nのループ

DP6-1-2

i = 1 のとき x = 9 から a[i-1](3) について調べる
( [3] のおもりを選んだ時に作れる和を調べる)

dp[9 - 3] = false -> 9 は作れない
dp[8 - 3] = false -> 8 は作れない
dp[7 - 3] = false -> 7 は作れない
dp[6 - 3] = false -> 6 は作れない
dp[5 - 3] = false -> 5 は作れない
dp[4 - 3] = false -> 4 は作れない
dp[3 - 3] = true -> 3 は作れる
dp[3] = true

[3]の組み合わせの和で[0,3] が作れる

DP6-1-3

i = 2 のとき x = 9 から a[i-1](2) について調べる
( [3, 2] のおもりを選んだ時に作れる和を調べる)

dp[9 - 2] = false -> 9 は作れない
dp[8 - 2] = false -> 8 は作れない
dp[7 - 2] = false -> 7 は作れない
dp[6 - 2] = false -> 6 は作れない
dp[5 - 2] = true -> 5 は作れる
dp[5] = true
dp[4 - 2] = false -> 4 は作れない
dp[3 - 2] = true -> 3 は作れない
dp[2 - 2] = true -> 2 は作れる
dp[3] = true

[3, 2]の組み合わせの和で[0, 2, 3, 5] が作れる

DP6-1-4

i = 3 のとき x = 9 から a[i-1](5) について調べる
( [3, 2, 5] のおもりを選んだ時に作れる和を調べる)

dp[9 - 5] = false -> 9 は作れない
dp[8 - 5] = true -> 8 は作れる
dp[8] = true
dp[7 - 5] = true -> 7 は作れる
dp[7] = true
dp[6 - 5] = false -> 6 は作れない
dp[5 - 5] = true -> 5 は作れる
dp[5] = true (元々 dp[5] = true)

[3, 2, 5]の組み合わせの和で[0, 2, 3, 5, 7, 8] が作れる

DP6-1-5

i = 4 のとき x = 9 から a[i-1](6) について調べる
( [3, 2, 5, 6] のおもりを選んだ時に作れる和を調べる)

dp[9 - 6] = false -> 9 は作れる
dp[8 - 6] = true -> 8 は作れる
dp[8] = true
dp[7 - 6] = false -> 7 は作れる
元々 dp[7] = true
dp[6 - 6] = false -> 6 は作れる
dp[6] = true

[3, 2, 5, 6]の組み合わせの和で[0, 2, 3, 5, 6, 7, 8, 9] が作れる

STEP2: 部分和問題 2 (paizaランク B 相当)

n種類, 各1個のおもりで重さxが何通りの組み合わせで作れるかを調べる問題です。

解答例

INPUT1 = <<~"EOS"
  5 10
  7
  3
  4
  3
  2
EOS
OUTPUT1 = <<~"EOS"
  3
EOS

def solve(input_lines)
  # 回答用の定数
  mod = 1_000_000_007

  # 入力受け取り
  input_lines = input_lines.split("\n")
  n, x = input_lines.shift.split.map(&:to_i)
  *a = input_lines.map(&:to_i)

  # dpテーブル初期化
  # おもりを選ばなければ重さの和 0 作ることができる
  dp = [1] + [0] * x

  # dpテーブル更新
  1.upto(n) do |i|
    x.downto(a[i - 1]) do |j|
      # a[i-1] を使って j を作れる組み合わせを足す
      dp[j] += dp[j - a[i - 1]]
    end
  end

  # x が作れる組み合わせ数 % 1_000_000_007 を返す
  dp[x] % mod
end

puts solve(STDIN.read)

# 確認用コード
puts solve(INPUT1)
# > 3

#        | j
#  i     | 0  1  2  3  4  5  6  7  8  9 10 |
#  - ( 0)| 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 |
# [1]( 7)| 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0 |
# [2]( 3)| 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1 |
# [3]( 4)| 1, 0, 0, 1, 1, 0, 0, 2, 0, 0, 1 |
# [4]( 3)| 1, 0, 0, 2, 1, 0, 1, 3, 0, 0, 3 |
# [5]( 2)| 1, 0, 1, 2, 1, 2, 2, 3, 1, 3, 3 |

整数n, 整数x, 配列aを受け取る。
dpに[1] + [0] * xを代入する。
(何も選ばなければ重さ0が作れる)
i = 1 ~ nで繰り返し処理を設定する。
- j = x ~ a[i - 1]で繰り返し処理を設定する。
  - dp[j] = true if dp[j - a[i - 1]]
    おもりa[i-1]を使って重さjが作れるならdp[j]に +1 する
dp[x] を 1,000,000,007 で割った余りを返す

入出力例1の処理

DP6-2-1

dp = [1] + [0] * x(10) で初期化

おもりを選ばなければ重さ0が作れる

ここからi = 1 ~ nのループ

DP6-2-2

i = 1 のとき x = 10 から a[i-1](7) について調べる
( [7] のおもりを選んだ時に作れる和を調べる)

dp[10] = dp[10](0) + dp[3](0) = 0
dp[9] = dp[9](0) + dp[2](0) = 0
dp[8] = dp[8](0) + dp[1](0) = 0
dp[7] = dp[7](0) + dp[0](1) = 1

[7]の組み合わせの和で

7 が 1通りの組み合わせで作れる

DP6-2-3

i = 2 のとき x = 10 から a[i-1](3) について調べる
( [7, 3] のおもりを選んだ時に作れる和を調べる)

dp[10] = dp[10](0) + dp[7](1) = 1
dp[9] = dp[9](0) + dp[6](0) = 0
dp[8] = dp[8](0) + dp[5](0) = 0
dp[7] = dp[7](1) + dp[4](0) = 1
dp[6] = dp[6](0) + dp[3](0) = 0
dp[5] = dp[5](0) + dp[2](0) = 0
dp[4] = dp[4](0) + dp[1](0) = 0
dp[3] = dp[7](0) + dp[0](1) = 1

[7, 3]の組み合わせの和で

3 が 1通りの組み合わせで作れる
7 が 1通りの組み合わせで作れる
10 が 1通りの組み合わせで作れる

DP6-2-4

i = 3 のとき x = 10 から a[i-1](4) について調べる
( [7, 3, 4] のおもりを選んだ時に作れる和を調べる)

dp[10] = dp[10](1) + dp[6](0) = 1
dp[9] = dp[9](0) + dp[5](0) = 0
dp[8] = dp[8](0) + dp[4](0) = 0
dp[7] = dp[7](1) + dp[3](1) = 2
dp[6] = dp[6](0) + dp[2](0) = 0
dp[5] = dp[5](0) + dp[1](0) = 0
dp[4] = dp[4](0) + dp[0](1) = 1

[7, 3, 4]の組み合わせの和で

3 が 1通りの組み合わせで作れる
4 が 1通りの組み合わせで作れる
7 が 2通りの組み合わせで作れる
10 が 1通りの組み合わせで作れる

DP6-2-5

i = 4 のとき x = 10 から a[i-1](3) について調べる
( [7, 3, 4, 3] のおもりを選んだ時に作れる和を調べる)

dp[10] = dp[10](1) + dp[7](2) = 3
dp[9] = dp[9](0) + dp[6](0) = 0
dp[8] = dp[8](0) + dp[5](0) = 0
dp[7] = dp[7](2) + dp[4](1) = 3
dp[6] = dp[6](0) + dp[3](1) = 1
dp[5] = dp[5](0) + dp[2](0) = 0
dp[4] = dp[4](1) + dp[1](0) = 1
dp[3] = dp[3](1) + dp[0](1) = 2

[7, 3, 4, 3]の組み合わせの和で

3 が 2通りの組み合わせで作れる
4 が 1通りの組み合わせで作れる
6 が 1通りの組み合わせで作れる
7 が 3通りの組み合わせで作れる
10 が 3通りの組み合わせで作れる

DP6-2-6

i = 5 のとき x = 10 から a[i-1](2) について調べる
( [7, 3, 4, 3, 2] のおもりを選んだ時に作れる和を調べる)

dp[10] = dp[10](1) + dp[8](0) = 3
dp[9] = dp[9](0) + dp[7](3) = 3
dp[8] = dp[8](0) + dp[6](1) = 1
dp[7] = dp[7](3) + dp[5](0) = 3
dp[6] = dp[6](1) + dp[4](1) = 2
dp[5] = dp[5](0) + dp[3](2) = 2
dp[4] = dp[4](1) + dp[2](0) = 1
dp[3] = dp[3](2) + dp[1](0) = 2
dp[2] = dp[2](0) + dp[0](1) = 1

[7, 3, 4, 3, 2]の組み合わせの和で

2 が 1通りの組み合わせで作れる
3 が 2通りの組み合わせで作れる
4 が 1通りの組み合わせで作れる
5 が 2通りの組み合わせで作れる
6 が 2通りの組み合わせで作れる
7 が 3通りの組み合わせで作れる
8 が 1通りの組み合わせで作れる
9 が 3通りの組み合わせで作れる
10 が 3通りの組み合わせで作れる

STEP3: 部分和問題 3 (paizaランク B 相当)

n種類, 各1個のおもりで重さxが作れる最小の組み合わせを調べる問題です。

解答例

INPUT1 = <<~"EOS"
  5 10
  7
  3
  4
  3
  2
EOS
OUTPUT1 = <<~"EOS"
  2
EOS

def solve(input_lines)
  # 入力受け取り
  input_lines = input_lines.split("\n")
  n, x = input_lines.shift.split.map(&:to_i)
  *a = input_lines.map(&:to_i)

  # dpテーブル初期化
  dp = [0] + [1.0 / 0] * x
  # おもりを選ばなければ重さの和 0 を作ることができる

  # dpテーブル更新
  1.upto(n) do |i|
    x.downto(a[i - 1]) do |j|
      # dp[i-1] を使って j を作れるなら
      unless dp[j - a[i - 1]].infinite?
        # dp[i-1] を 使った場合:使わない場合 でおもりの数が少ない方を記録
        dp[j] = [dp[j], dp[j - a[i - 1]] + 1].min
      end
    end
  end

  # 和で重さ x を作れる最小の個数 , 作れない場合 -1 を返す
  dp[x].infinite? ? -1 : dp[x]
end

#puts solve(STDIN.read)

# puts solve(INPUT1)
# > 2

#        | j
#  i     | 0  1  2  3  4  5  6  7  8  9 10 |
#  - ( 0)| 0, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞ |
# [1]( 7)| 0, ∞, ∞, ∞, ∞, ∞, ∞, 1, ∞, ∞, ∞ |
# [2]( 3)| 0, ∞, ∞, 1, ∞, ∞, ∞, 1, ∞, ∞, 2 |
# [3]( 4)| 0, ∞, ∞, 1, 1, ∞, ∞, 1, ∞, ∞, 2 |
# [4]( 3)| 0, ∞, ∞, 1, 1, ∞, 2, 1, ∞, ∞, 2 |
# [5]( 2)| 0, ∞, 1, 1, 1, 2, 2, 1, 3, 2, 2 |

整数n, 整数x, 配列aを受け取る。
dpに[0] + [1.0/0(∞)] * xを代入する。
(何も選ばなければ重さ0が作れる)
i = 1 ~ nで繰り返し処理を設定する。
- j = x ~ a[i - 1]で繰り返し処理を設定する。
  - dp[j] = [dp[j], dp[j - a[i - 1]] + 1].min (dp[j - a[i - 1]] != ∞)
    dp[j] と dp[j- a[i -1]]+1 でおもりの数が少ない方で更新する
dp[x] を返す。（∞のままなら重さx作れない）

入出力例1の処理

DP6-3-1

dp = [0] + [1.0/0(∞)] * x(10) で初期化

おもりを選ばなければ重さ0が作れる

ここからi = 1 ~ nのループ

DP6-3-2

i = 1 のとき x = 10 から a[i-1](7) について調べる
( [7] のおもりを選んだ時に作れる和を調べる)

dp[10] = [dp[10](∞), dp[3](∞)].min = ∞
dp[9] = [dp[9](∞), dp[2](∞)].min = ∞
dp[8] = [dp[8](∞), dp[1](∞)].min = ∞
dp[7] = [dp[7](∞), dp[0](0)+1].min = 1

[7]の組み合わせから

7 が最小おもり1個で作れる

DP6-3-3

i = 2 のとき x = 10 から a[i-1](3) について調べる
( [7, 3] のおもりを選んだ時に作れる和を調べる)

dp[10] = [dp[10](∞), dp[7](1+1)].min = 2
dp[9] = [dp[9](∞), dp[6](∞)].min = ∞
dp[8] = [dp[8](∞), dp[5](∞)].min = ∞
dp[7] = [dp[7](1), dp[4](∞)].min = 1
dp[6] = [dp[6](∞), dp[3](∞)].min = ∞
dp[5] = [dp[5](∞), dp[2](∞)].min = ∞
dp[4] = [dp[4](∞), dp[1](∞)].min = ∞
dp[3] = [dp[3](∞), dp[0](0)+1].min = 1

[7, 3]の組み合わせから

3 が最小おもり1個で作れる
7 が最小おもり1個で作れる
10 が最小おもり2個で作れる

DP6-3-4

i = 3 のとき x = 10 から a[i-1](4) について調べる
( [7, 3, 4] のおもりを選んだ時に作れる和を調べる)

dp[10] = [dp[10](2), dp[6](∞)].min = 2
dp[9] = [dp[9](∞), dp[5](∞)].min = ∞
dp[8] = [dp[8](∞), dp[4](∞)].min = ∞
dp[7] = [dp[7](1), dp[3](1)+1].min = 1
dp[6] = [dp[6](∞), dp[2](∞)].min = ∞
dp[5] = [dp[5](∞), dp[1](∞)].min = ∞
dp[4] = [dp[4](∞), dp[0](∞)+1].min = 1

[7, 3, 4]の組み合わせから

3 が最小おもり1個で作れる
4 が最小おもり1個で作れる
7 が最小おもり1個で作れる
10 が最小おもり2個で作れる

DP6-3-5

i = 4 のとき x = 10 から a[i-1](3) について調べる
( [7, 3, 4, 3] のおもりを選んだ時に作れる和を調べる)

dp[10] = [dp[10](2), dp[7](1)+1].min = 2
dp[9] = [dp[9](∞), dp[6](∞)].min = ∞
dp[8] = [dp[8](∞), dp[5](∞)].min = ∞
dp[7] = [dp[7](1), dp[4](1)+1].min = 1
dp[6] = [dp[6](∞), dp[3](1)+1].min = 2
dp[5] = [dp[5](∞), dp[2](∞)].min = ∞
dp[4] = [dp[4](1), dp[1](∞)].min = 1
dp[3] = [dp[3](1), dp[0](0)+1].min = 1

[7, 3, 4, 3]の組み合わせから

3 が最小おもり1個で作れる
4 が最小おもり1個で作れる
6 が最小おもり2個で作れる
7 が最小おもり1個で作れる
10 が最小おもり2個で作れる

DP6

i = 5 のとき x = 10 から a[i-1](2) について調べる
( [7, 3, 4, 3, 2] のおもりを選んだ時に作れる和を調べる)

dp[10] = [dp[10](2), dp[8](∞)].min = 2
dp[9] = [dp[9](∞), dp[7](1)+1].min = 2
dp[8] = [dp[8](∞), dp[6](2)+1].min = 3
dp[7] = [dp[7](1), dp[5](∞)].min = 1
dp[6] = [dp[6](2), dp[4](1)+1].min = 2
dp[5] = [dp[5](∞), dp[3](1)+1].min = 2
dp[4] = [dp[4](1), dp[2](∞)].min = 1
dp[3] = [dp[3](1), dp[1](∞)].min = 1
dp[2] = [dp[2](∞), dp[0](0)+1].min = 1

[7, 3, 4, 3, 2]の組み合わせから

2 が最小おもり1個で作れる
3 が最小おもり1個で作れる
4 が最小おもり1個で作れる
5 が最小おもり2個で作れる
6 が最小おもり2個で作れる
7 が最小おもり1個で作れる
8 が最小おもり3個で作れる
9 が最小おもり2個で作れる
10 が最小おもり2個で作れる

FINAL問題: 部分和問題 4 (paizaランク B 相当)

※ paizaレベルアップ問題集 DPメニューより

問題

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

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

入力される値

n x
a_1
a_2
...
a_n

1行目に、おもりの種類数 n と目標とする重さの和 x が半角スペース区切りで与えられます
続く n 行のうち i 行目では、おもり i の重さ a_i が与えられます。

入力値最終行の末尾に改行が１つ入ります。

期待する出力

重さの和が x となるようにおもりを選ぶことができるなら yes と、できないなら no と出力してください。

また、末尾に改行を入れ、余計な文字、空行を含んではいけません。

条件

すべてのテストケースにおいて、以下の条件をみたします。

1 ≦ n ≦ 100
1 ≦ x ≦ 1,000
1 ≦ a_i ≦ 100

入力例1: 5 10
9
3
4
11
8

出力例1: yes

攻略ポイント

ポイント

無限個存在するおもりから任意の数を使う処理を考える

問題を解く流れ

入出力例をコピペしてヒアドキュメントで変数に代入し、データを確認します。正しく受け取れていれば確認用コードは削除します。

INPUT1 = <<~"EOS"
  5 10
  9
  3
  4
  11
  8
EOS
OUTPUT1 = <<~"EOS"
  yes
EOS

# 確認用コード
p INPUT1
# > "5 10\n9\n3\n4\n11\n8\n"
p OUTPUT1
# > "yes\n"

続いて、問題を解くsolveメソッドを変数の下に定義し、入力データを受け取る処理を書きます。

def solve(input_lines)
  # 入力受け取り
  input_lines = input_lines.split("\n")
  n, x = input_lines.shift.split.map(&:to_i)
  *a = input_lines.map(&:to_i)

  # 確認用コード
  [n, x, a]
end

# 確認用コード
p solve(INPUT1)
# > [5, 10, [9, 3, 4, 11, 8]]

データが正しく受け取れていれば、solve メソッドに処理を追加していきます。

整数n, 整数x, 配列aを受け取る。
dpに[true] + [false] * xを代入する。
(何も選ばなければ重さ0が作れる)
i = 1 ~ nで繰り返し処理を設定する。
- j = a[i - 1] ~ xで繰り返し処理を設定する。
  (増加方向にループを回すのがポイント)
  - dp[j] = true if dp[j - a[i - 1]]
    おもりa[i-1]を使って重さjが作れるならdp[j]をtrueで更新する
- dp[x]がtrue ならループを抜ける
dp[x]がtrueならYes、falseならNoを返す

def solve(input_lines)
  # 入力受け取り
  input_lines = input_lines.split("\n")
  n, x = input_lines.shift.split.map(&:to_i)
  *a = input_lines.map(&:to_i)

  # dpテーブル初期化
  # おもりを選ばなければ重さの和 0 作ることができる
  dp = [true] + [false] * x

  # dpテーブル更新
  1.upto(n) do |i|
    a[i - 1].upto(x) do |j|
      # a[i-1] を使って おもさ j が作れるか
      dp[j] = true if dp[j - a[i - 1]]
    end
    # x が作れるならループを抜ける
    break if dp[x]
  end

  # 確認用コード
  dp
end

# 確認用コード
# p solve(INPUT1)
# > [true, false, false, true, true, false, true, true, true, true, true]
p solve(INPUT1) == OUTPUT1
# > false

dpテーブルの内容が良さそうなら、重さx が作れるなら "yes"、作れないなら"no"を出力すれば完成です。
p solve(INPUT1) == OUTPUT1 -> true を確認するために、yes/no の末尾に改行を加えます。

def solve(input_lines)
  # 入力受け取り
  input_lines = input_lines.split("\n")
  n, x = input_lines.shift.split.map(&:to_i)
  *a = input_lines.map(&:to_i)

  # dpテーブル初期化
  # おもりを選ばなければ重さの和 0 作ることができる
  dp = [true] + [false] * x

  # dpテーブル更新
  1.upto(n) do |i|
    a[i - 1].upto(x) do |j|
      # a[i-1] を使って おもさ j が作れるか
      dp[j] = true if dp[j - a[i - 1]]
    end
    # x が作れるならループを抜ける
    break if dp[x]
  end

  # 重さ x が作れるなら "yes\n", 作れないなら "no\n" を返す
  dp[x] ? "yes\n" : "no\n"
end

# 確認用コード
p solve(INPUT1)
# > "yes\n"
p solve(INPUT1) == OUTPUT1
# > true

入出力例での動作確認が出来ましたので、標準入力からのデータ受け取りに変更して、手動で動作確認をしたら提出します。
複数行のデータ受け取りなので STDIN.read を使います。（入力終了は Ctrl+D 又は Ctrl+Z)

解答コード

def solve(input_lines)
  # 入力受け取り
  input_lines = input_lines.split("\n")
  n, x = input_lines.shift.split.map(&:to_i)
  *a = input_lines.map(&:to_i)

  # dpテーブル初期化
  # おもりを選ばなければ重さの和 0 作ることができる
  dp = [true] + [false] * x

  # dpテーブル更新
  1.upto(n) do |i|
    a[i - 1].upto(x) do |j|
      # a[i-1] を使って おもさ j が作れるか
      dp[j] = true if dp[j - a[i - 1]]
    end
    # x が作れるならループを抜ける
    break if dp[x]
  end

  # 重さ x が作れるなら "yes\n", 作れないなら "no\n" を返す
  dp[x] ? "yes\n" : "no\n"
end

puts solve(STDIN.read)

入出力例1の処理

DP6-4-1

dp = [true] + [false] * x(10) で初期化

おもりを選ばなければ重さの和 0 作ることができる

ここからi = 1 ~ nのループ

DP6-4-2

i = 1 のとき a[i-1](9) から x(10)について調べる
( [9] のおもりを選んだ時に作れる和を調べる)

dp[9 - 9] = true -> 9 は作れる
dp[9] = true
dp[10 - 9] = false -> 10 は作れない

[9]の組み合わせの和で[0,9] が作れる

DP6-4-3

i = 2 のとき a[i-1](3) から x(10)について調べる
( [9, 3] のおもりを選んだ時に作れる和を調べる)

dp[3 - 3] = true -> 3 は作れる
dp[3] = true
dp[4 - 3] = false -> 4 は作れない
dp[5 - 3] = false -> 5 は作れない
dp[6 - 3] = true -> 6 は作れる
dp[6] = true
dp[7 - 3] = false -> 7 は作れない
dp[8 - 3] = false -> 8 は作れない
dp[9 - 3] = true -> 9 は作れる
dp[9] = true (元々 dp[9] = true)
dp[10 - 9] = false -> 10 は作れない

[9, 3]の組み合わせの和で[0, 3, 6, 9] が作れる

DP6-4-4

i = 3 のとき a[i-1](4) から x(10)について調べる
( [9, 3, 4] のおもりを選んだ時に作れる和を調べる)

dp[4 - 4] = true -> 4 は作れる
dp[4] = true
dp[5 - 4] = false -> 5 は作れない
dp[6 - 4] = false -> 6 は作れる
元々 dp[6] = true
dp[7 - 4] = true -> 7 は作れる
dp[7] = true
dp[8 - 4] = true -> 8 は作れる
dp[8] = true
dp[9 - 4] = false -> 8 は作れる
元々 dp[9] = true
dp[10 - 4] = true -> 10 は作れる
dp[10] = true

[9, 3, 4]の組み合わせの和で[0, 3, 4, 6, 7, 8, 9, 10] が作れる

今回のまとめ

セクション6は配列から要素を任意の数を選択して、指定された和を作れるかを判定する問題でした。

dpテーブルを順方向に検索することで同じおもりを複数個選択する状態を実装しました。
今回でDPメニューは終了です。お疲れ様でした！

【PR】アルゴリズム学習でお世話になった本

アルゴリズム関連の技術書は大抵C/C++で書かれていますが、ある程度プログラムが出来れば、処理の流れは理解することが出来ます。

通称: 螺旋本。C++で解説されています。AOJ(Aizu Online Judge)を運営している会津大学の渡辺准教授が書いた本です。データ構造や計算量の内容から丁寧に書いてありますのでアルゴリズム学習の最初の参考書としてオススメです。

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造 [ 渡部有隆 ]

posted with カエレバ

楽天市場

Amazon

Yahooショッピング

通称: 蟻本。C++で解説されています。競技プログラミング中級者の定番書と言われていて、競技プログラミングで利用できる色々なアルゴリズムを学ぶことが出来ます。かなり高度な内容も含まれているので1冊分を完全に理解するのにはかなりの時間がかかりそうですが、手元に置いて何度も読み返しています。

プログラミングコンテストチャレンジブック第2版問題解決のアルゴリズム活用力とコーディングテクニッ [ 秋葉拓哉 ]

posted with カエレバ

楽天市場

Amazon

Yahooショッピング

通称: チーター本。C#, C++, JAVAでTopcoderの問題を解説しています。初心者～中級者向けに書かれているので解説が非常に丁寧です。

最強最速アルゴリズマー養成講座プログラミングコンテストTopCoder攻略ガイド【電子書籍】[ 高橋直大 ]

posted with カエレバ

楽天市場

Amazon

Yahooショッピング

Python3でアルゴリズムを解説している本です。講義スタイルの本で、図やフローチャートを使ってアルゴリズムとデータ構造についてしっかりと説明されています。代わりにコードは少なめです。Pythonコードが読めなくても十分理解できると思います。

Pythonで体験してわかるアルゴリズムとデータ構造 [ 西澤弘毅 ]

posted with カエレバ

楽天市場

Amazon

Yahooショッピング

-paiza, プログラミング
-B級, 動的計画法, 部分和

comment

: paiza プログラミング

[Ruby|Python]paiza 標準出力メニュー【文字列の出力】

今回はpaiza 標準入力メニューセクション3【文字列の出力】を解説します。セクション3は、指定された文字列を改行区切りや半角スペース区切りで出力する問題です。目次本記事で使用しているメソッドにつ ...

: Ruby プログラミング

[Ruby] 標準出力（データを任意に整形して出力する）

こんにちは！じゃいごテックのあつしです。 paizaなどの競技プログラミングでは標準入力でデータ受け取って、標準出力で処理結果を回答します。 Rubyにはいくつか標準出力メソッドが用意されていますが、 ...

: paiza プログラミング

[Ruby|Python]paiza 標準入力メニューセクション1～3（文字列）

今回はpaiza 標準入力メニューセクション1～3（文字列の入力）を解説します。セクション１は複数行の入力データがあった場合に各行の文字列を受け取る問題です。セクション２・セクション３は、1行の中 ...

: Ruby プログラミング

[Ruby]配列の基本操作2

こんにちは！じゃいごテックのあつしです。配列を自由に扱うことが出来ればアルゴリズム問題も解けるようになるかと思います！「配列の基本操作」後半も張り切っていきましょう！目次配列の要素数を数える配列 ...

: paiza プログラミング

[Ruby|Python]paiza 標準出力メニュー【特定の文字で区切り 1 行で出力】

今回はpaiza 標準入力メニューセクション5【特定の文字で区切り 1 行で出力】を解説します。セクション5は、任意の文字列で区切って1から入力された整数n までを改行区切りで出力する問題です。目 ...

PREV: [Ruby]paiza DPメニュー部分列
NEXT: [アルゴリズム(Ruby)]線形探索法（リニアサーチ）の解説

[Ruby]paiza DPメニュー 部分和

STEP問題 を解いてみる

STEP1: 部分和問題 1 (paizaランク B 相当)

処理の流れ

STEP2: 部分和問題 2 (paizaランク B 相当)

解答例

入出力例1の処理

STEP3: 部分和問題 3 (paizaランク B 相当)

解答例

入出力例1の処理

FINAL問題: 部分和問題 4 (paizaランク B 相当)

問題

攻略ポイント

問題を解く流れ

解答コード

入出力例1の処理

今回のまとめ

【PR】アルゴリズム学習でお世話になった本

[Ruby]paiza DPメニュー部分和

STEP問題を解いてみる