動的計画法がわからない ~その1~

Python

動的計画法、ダイナミックプログラミング、DP法・・・

色々言い方はあるけど、まぁ理解できない。

理解できないを放置していても理解できるようにならないのでイメージを書き出していって問題点を洗い出しときたい。

もしこの記事読んでくれてる人いたらどこでもいいのであそこ間違ってるよとか教えてほしい。

abc204_d Cooking

いきなりネタバレ要素で申し訳ない。この問題を参考にして行きたい。

A - Frog 1
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

前提条件

N = 料理の品数

T[1]・・・T[N] = それぞれの料理にかかる時間

料理は2品まで一緒に作れるとして

N品目作ったときの最短時間を求めたい

例えば、

N = 3、T = [3, 5, 8]

とかだと

コンロAで8分作ってる間に

コンロBで3分作って5分作る

で8分で完成する。

イメージ

多分各パターンを組み合わせたリストみたいなの作る。

それから条件に合うものを探索掛けて(この場合一番時間が短いもの)答えとして提出する。

各パターンを組み合わせたリストの作り方?そんなものがあるとして作り方がわからない。

解説見た

要はトータル作業時間/2に一番近い数値を出せばいいらしい

コード見ながら考える

#まず数値入力
n = 3 #int(input()) #品数
t = [3, 2, 2] #list(map(int,input().split())) #各料理時間
#トータル作業時間を求める
total_t = sum(t)
#トータル作業時間の半分の値も求めておく
target_t = int(total_t / 2)

#でかい配列を用意する(0は無理、1なら可能のフラグ管理)
dp = [[0] * (total_t + 1) for _ in range(n + 1)]
#[0] * (total_t + 1) *多分時間経過を表している、0分からtotal_t分までの0(無理フラグ)が続いているリスト?
#for _ in range (n + 1) *上で作ったものを品数+1個複製させている?
#                          0個作る場合からn個作る場合までを作らせているっぽい

dp[0][0] = 1
dp[1][0] = 1
#どういう表示になるのか知りたかったから位置に深い意味はない
print(dp)

とりあえずここらへんで「配列0の0番目の要素と1の0番目の要素を1」にして表示させてみた

0, 1, 2, 3, 4, 5, 6, 7 経過時間(リスト[t]の合計時間に0分を入れるために+1したもの)

[[1, 0, 0, 0, 0, 0, 0, 0] 何も作らないパターン(0分で終わる)

[1, 0, 0, 1, 0, 0, 0, 0] t[0]を作る(3分で終わるからdp[1][3]のフラグが1に変わる)

[1, 0, 1, 1, 0, 1, 0, 0] t[0],t[1]を作る(2分で作るから2分のフラグを変えて3分+2分にも
            フラグ立てる
[1, 0, 1, 1, 1, 1, 0, 1] t[0],t[1],t[2]を作る(最終的にこんな感じでフラグが立つ?)

なんか一番最後の配列が重要な気がする。

トータル時間が7分で半分にすると3分半だから答えは4分になるのかな?

for i in range(n): #品数でiを回す。先程の表を下に降りていくイメージ?
    for j in range(total_t+1): #経過時間でjを回す
        if dp[i][j] == 1: #もしdp[0][0]が1なら(実際に1
            dp[i+1][j] = 1 #その下のdp[1][0]は1のフラグが立つはず
            dp[i+1][j+t[i]] = 1 #dp[1][0+3分(t[1]の場合の料理時間3分)]は1のフラグが立つ

for i in range(target_t,total_t+1): #半分より前半は無視して良いのでtarget_tから始める
    if dp[-1][i] == 1: #最終行から始めて[-1]、トータル作業時間の半分からトータル作業時間+1まで調べる
        print(i) #フラグが立っているiを見つけたらiをプリントして
        break #処理を終わらせる

最終的なコード

#まず数値入力
n = int(input()) #品数
t = list(map(int,input().split())) #各料理時間
#トータル作業時間を求める
total_t = sum(t)
#トータル作業時間の半分の値も求めておく
target_t = total_t - total_t//2 # //2で引くことで小数点が削られて半分より少し大きくなる可能性がある

#でかい配列を用意する(0は無理、1なら可能の二進法)
dp = [[0] * (total_t + 1) for _ in range(n + 1)]
#[0] * (total_t + 1) *多分時間経過を表している、0分からtotal_t分までの0(無理フラグ)が続いているリスト?
#for _ in range (n + 1) *上で作ったものを品数+1個複製させている?
#                          0個作る場合からn個作る場合までを作らせているっぽい

dp[0][0] = 1
#dp[1][0] = 1
#どういう表示になるのか知りたかったから位置に深い意味はない
#print(dp)

for i in range(n): #品数でiを回す。先程の表を下に降りていくイメージ?
    for j in range(total_t+1): #経過時間でjを回す
        if dp[i][j] == 1: #もしdp[0][0]が1なら(実際に1
            dp[i+1][j] = 1 #その下のdp[1][0]は1のフラグが立つはず
            dp[i+1][j+t[i]] = 1 #dp[1][0+3分(t[1]の場合の料理時間3分)]は1のフラグが立つ

for i in range(target_t,total_t+1): #半分より前半は無視して良いのでtarget_tから始める
    if dp[-1][i] == 1: #最終行から始めて[-1]、トータル作業時間の半分からトータル作業時間+1まで調べる
        print(i) #フラグが立っているiを見つけたらiをプリントして
        break #処理を終わらせる

多分これでいけると思うけどどうなんだろう?

一応自分が納得できるように解説入れてみた。

予想とあってるのかどうかもわからないけどなんとなく理解出来た気がする。

感想

なんとなくわかったようなわからなかったような・・・

ちなみにこの問題の解き方を部分和っていうらしい。他にもあるみたいなのでまた解説見ながら理解深める記事を書きたいと思います。

ここの解釈間違ってるよ?とかあれば教えて下さいね。

コメント

タイトルとURLをコピーしました