第114回【Python】部分和問題 3、【部分和】部分和問題 4

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

はじめに

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

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

Python の勉強をしているのか、数学の問題を解いているのかわからなくなってきました。いや、元々好きなので、楽しいんですけど。昔々に書いた総当たりコードを書き直したら、爆速で終わりました。もっと勉強しようと反省です。

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

部分和問題 3

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

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

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

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

出力例

2

頭の中だけで理解しようとすると混乱してくる・・・。

Python
n,x = map(int,input().split())
A = [int(input()) for _ in range(n)]
dp = [n+1] * (x+1)
dp[0] = 0
for a in A:
    for i in range(x,a-1,-1):
        if dp[i-a] != n+1:
            dp[i] = min(dp[i],dp[i-a]+1)
if dp[x] == n+1:
    print(-1)
else:
    print(dp[x])
VBA
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) = 0
For i = 1 To x
    dp(i) = N + 1
Next
For Each v In A
    For i = x To v Step -1
        If dp(i - v) <> N + 1 Then
            dp(i) = Application.WorksheetFunction.Min(dp(i), dp(i - v) + 1)
        End If
    Next
Next
If dp(x) = N + 1 Then
    Debug.Print -1
Else
    Debug.Print dp(x)
End If

【部分和】部分和問題 4

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

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

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
9
3
4
11
8

出力例

yes

これまでは、存在するおもりだけを用いていたけれど、今回は、幾つでも使っていいらしい。

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 i in range(a,x+1):
        if dp[i-a]:
            dp[i] = 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 = v To x
        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

最後に

これで、「DP メニュー」は終了です。覚えていれば絶対にどこかで使うことができると思うので、理解できるまで何回も解いてみるのが良いと思います。

次は、「クラス・構造体メニュー」に挑戦予定。VBA でクラスを使うことはあっても、構造体を使うことはあまりないので自信がない。ちょっと時間をかけて勉強するしかなさそうです。

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

Pythonpaiza,学習,Python

Posted by LeoSaki