第113回【Python】部分和問題 1、部分和問題 2

現在取り組んでいるのは、paiza ラーニング問題集「DP メニュー」になります。

はじめに

猫とキャンプと野球観戦と AWS が大好きな旦那、LeoSaki です。モフモフしたい。

Python をゼロから勉強してみよう、のコーナー 113 回目です。

やるべきことが多くて、何から行うべきかの順序立てを行う際に、もちろん、期限が近いものを優先する必要はありますが、面倒なものを優先して行う癖があります。しかし、LunaSaki（嫁）は、簡単なものから終わらたい人です。時々衝突します。

それでは、今日も頑張ってみようと思います。

部分和問題 1

1 ~ n の番号がついた n 個のおもりがあり、おもり i の重さは a_i です。
おもりを何個か選んで重さの和が x となるようにすることができるかどうか判定してください。なお、同じおもりを2個以上選ぶことはできません。

(ヒント)

おもり 1 ~ n を用いて重さの和を x となるようにすることができるか、という問題を考えるために、部分問題としておもり 1 ~ n-1 を用いて重さの和を x となるようにすることができるか、という問題を考えてみましょう。

n-1 までのおもりを用いて重さの和を x または x-a_n となるようにすることができれば、おもり 1 ~ n を用いて重さの和を x となるようにすることができることがわかります。よって、最初はおもり 1 のみを使えることにして問題を解き、次にその結果を利用しておもり 1 ~ 2 を使えることにして問題を解く、ということを n まで繰り返せば、元の問題が解けそうです。

dp_k[x] を、おもり k までを用いて重さの和が x となるようにすることができるかどうかを表す真偽値とすると、上で考察した関係は漸化式で表すと dp_k[x] = (dp_{k-1}[x] or dp_{k-1}[x-a_k]) となります。

dp_1, dp_2, … と順に dp_n まで計算すれば問題の答えが求まります。dp_1 から dp_n のそれぞれに対応する n 本の1次元配列 (もしくはこれに相当する2次元配列) を使って実装してもよいのですが、dp_k[x] を求めるには dp_{k-1}[x] と dp_{k-1}[x-a_k] さえわかっていれば十分であることを踏まえると、ループの回し方を以下の様に工夫することで、これまでと同じように1本の1次元配列で解くことができます。

for i = 0 to x
    dp[i] <- false

dp[0] <- true   // おもりを選ばなければ、重さの和を0とすることができる

for i = 1 to n  // おもり i までのおもりを使って
    for j = x down to a_i    // 重さの和を j とすることができるか？
        if dp[j-a_i] is true then
            dp[j] <- true   

if dp[x] is true then
    print "yes"
else
    print "no"

j を x から a_i へ減らす方向にループを回していることに注意してください。逆に a_i から x へ 増やす方向にループを回すと正しく答えが求まらない可能性があります。理由を考えてみましょう (ヒント: n = 1, a_1 = 5, x = 10 のとき、ループの回し方によって答えはどうなるか？)

n x
a_1
a_2
...
a_n

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

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

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

入力例

5 19
7
18
5
4
8

出力例

yes

全パターンの組み合わせを作って、x になるかどうかを計算するやつ。個数が増えれば太刀打ちできなくなります。昔はそれで躓きました。

Python
n,x = map(int,input().split())
A = [int(input()) for _ in range(n)]
dp = [False] * (x+1)
dp[0] = True
for a in A:
    for j in range(x,a-1,-1):
        if dp[j-a]:
            dp[j] = True
if dp[x]:
    print('yes')
else:
    print('no')
VBA
NX = Split(Cells(1, 1), " ")
N = Val(NX(0))
x = Val(NX(1))
Dim A() As Integer, dp() As Boolean
ReDim A(N - 1)
ReDim dp(x)
For i = 0 To N - 1
    A(i) = Cells(i + 2, 1)
Next
dp(0) = True
For Each v In A
    For i = x To v Step -1
        If dp(i - v) Then
            dp(i) = True
        End If
    Next
Next
If dp(x) Then
    Debug.Print "yes"
Else
    Debug.Print "no"
End If

部分和問題 2

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

おもりを何個か選んで重さの和が x となるようにする方法が何通りあるか求めてください。なお、同じおもりを2個以上選ぶことはできません。

重さが同じおもりが複数存在する場合、それらは区別して別のものとして扱うことにします。

答えは非常に大きくなる可能性があるので、答えを 1,000,000,007 で割った余りで出力してください。

n x
a_1
a_2
...
a_n

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

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

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

入力例

5 10
7
3
4
3
2

出力例

3

しっかり理解するためには、手書きとかで一つずつ分析してみた方が良いと思う。なんか余計なことをしているように思えて、これが一番最良の方法だと気づくかもしれない。

Python
mod = 1000000007
n,x = map(int,input().split())
A = [int(input()) for _ in range(n)]
dp = [0] * (x+1)
dp[0] = 1
for a in A:
    for i in range(x,a-1,-1):
        dp[i] += dp[i-a]
        dp[i] %= mod
print(dp[x])
VBA
m = 1000000007
NX = Split(Cells(1, 1), " ")
N = Val(NX(0))
x = Val(NX(1))
Dim A() As Integer, dp() As Long
ReDim A(N - 1)
ReDim dp(x)
For i = 0 To N - 1
    A(i) = Cells(i + 2, 1)
Next
dp(0) = 1
For Each v In A
    For i = x To v Step -1
        dp(i) = dp(i) + dp(i - v)
        dp(i) = dp(i) Mod m
    Next
Next
Debug.Print dp(x)

最後に

やっていることは理解できるのだけれど、これをさらさらとコードで書けと言われると、ちょっと自信ないです。結構余計なことをしているように見えて、それでいて総当たりで考えるよりも全然早いスピードで解けてしまう。

数学的な面白さがあって、好きな問題です。しかし、この問題について説明してくださいと言われたら一目散に逃げだす気がします。

引き続き、よろしくお願いいたします！

Python学習,Python,paiza

Posted by LeoSaki