第110回【Python】最安値を達成するには 3、【最安値】最安値を達成するには 4

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

はじめに

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

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

110 って聞いて、なぜか身構えるのは、おまわりさんを思い出してしまうからでしょうか。やましいことはしていない!

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

最安値を達成するには 3

八百屋にて、りんご x 個が a 円で、りんご y 個が b 円で売られています。

りんごの買い方を工夫したとき、最終的に n 個のりんごを手に入れるために必要な金額の最小値はいくらでしょうか。なお、買い方を工夫した結果、買ったりんごが n+1 個以上になってもよいものとします。

n x a y b

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

・ 1 ≦ n ≦ 1,000
・ 1 ≦ x ≦ 1,000
・ 1 ≦ y ≦ 1,000
・ x < y
・ 1 ≦ a ≦ 10,000
・ 1 ≦ b ≦ 10,000
・ a < b


入力例

4 2 110 5 200

出力例

200

前回の問題のさらにマスクされた部分が増えたバージョン。冷静に考えると簡単。

Python
n,x,a,y,b = map(int,input().split())
dp = [10000000] * (n+y)
dp[0] = 0
dp[1] = a
for i in range(2,n+y):
    if i >= x:
        dp[i] = min(dp[i],dp[i-x] + a)
    if i >= y:
        dp[i] = min(dp[i],dp[i-y] + b)
print(min(dp[n:]))
VBA
NXAYB = Split(Cells(1, 1), " ")
N = Val(NXAYB(0))
x = Val(NXAYB(1))
A = Val(NXAYB(2))
Y = Val(NXAYB(3))
b = Val(NXAYB(4))
Dim dp() As Long
ReDim dp(N + Y)
dp(0) = 0
dp(1) = A
For i = 2 To N + Y
    dp(i) = 10000000
    If i >= x Then
        dp(i) = Application.WorksheetFunction.Min(dp(i), dp(i - x) + A)
    End If
    If i >= Y Then
        dp(i) = Application.WorksheetFunction.Min(dp(i), dp(i - Y) + b)
    End If
Next
For i = N To N + Y
    dp(i - N) = dp(i)
Next
ReDim Preserve dp(UBound(dp) - N)
Debug.Print Application.WorksheetFunction.Min(dp)

【最安値】最安値を達成するには 4

八百屋にて、りんご x 個が a 円で、りんご y 個が b 円で、りんご z 個が c 円で売られています。

りんごの買い方を工夫したとき、n 個のりんごを手に入れるために必要な金額の最小値はいくらでしょうか。なお、買い方を工夫した結果、買ったりんごが n+1 個以上になってもよいものとします。

n x a y b z c

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

・ 1 ≦ n ≦ 1,000
・ 1 ≦ x ≦ 1,000
・ 1 ≦ y ≦ 1,000
・ 1 ≦ z ≦ 1,000
・ x < y < z
・ 1 ≦ a ≦ 10,000
・ 1 ≦ b ≦ 10,000
・ 1 ≦ c ≦ 10,000
・ a < b < c


入力例

9 2 100 3 125 5 200

出力例

375

まとめて売られているリンゴって、それぞれ種類が違ったりするんだろうか。それとも、まとめ売りだからボリュームディスカウントしてるんだろうか。

Python
n,x,a,y,b,z,c = map(int,input().split())
dp = [10000000] * (n+z)
dp[0] = 0
dp[1] = a
for i in range(2,n+z):
    if i >= x:
        dp[i] = min(dp[i],dp[i-x] + a)
    if i >= y:
        dp[i] = min(dp[i],dp[i-y] + b)
    if i >= z:
        dp[i] = min(dp[i],dp[i-z] + c)
print(min(dp[n:]))
VBA
NXAYBZC = Split(Cells(1, 1), " ")
N = Val(NXAYBZC(0))
x = Val(NXAYBZC(1))
A = Val(NXAYBZC(2))
Y = Val(NXAYBZC(3))
b = Val(NXAYBZC(4))
Z = Val(NXAYBZC(5))
C = Val(NXAYBZC(6))
Dim dp() As Long
ReDim dp(N + Z)
dp(0) = 0
dp(1) = A
For i = 2 To N + Z
    dp(i) = 10000000
    If i >= x Then
        dp(i) = Application.WorksheetFunction.Min(dp(i), dp(i - x) + A)
    End If
    If i >= Y Then
        dp(i) = Application.WorksheetFunction.Min(dp(i), dp(i - Y) + b)
    End If
    If i >= Z Then
        dp(i) = Application.WorksheetFunction.Min(dp(i), dp(i - Z) + C)
    End If
Next
For i = N To N + Z
    dp(i - N) = dp(i)
Next
ReDim Preserve dp(UBound(dp) - N)
Debug.Print Application.WorksheetFunction.Min(dp)

最後に

これは、メモでもとりながら。冷静に分析して理解しておくと、いろいろな手法で利用できると思う。実際、このやり方を知っていたおかげで書けたコードもあった。

VBA でこれをやろうとは思わなかったけれど、やってみると出来るもんですね。さすがに VBA でこれを利用することがあるかどうかは思い浮かばない。

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

Python学習,Python,paiza

Posted by LeoSaki