ナップサック問題ふたたび〜dp利用〜【競技プログラミング】

はじめに

• ナップサック問題は、過去に2回投稿してた。
  • 初回は、dpを使って「最大許容重量Wが大きくない場合」を解いて、
  • 二回目は、分枝限定法を使って、「Wも価値の合計値Vも大きい場合」をカバーした。
• 分枝限定法を使えば、WやVが大きくても問題ないんだから、もう　十分でしょと思ったけど、やはり、ナップサック問題は基本中の基本なので、「Wは大きいけど、Vは大きくない場合」をdpで解きたいと思う。
• それに、dpで解いていた「Wが大きくない場合」の解法が分かりづらかったので、今回、改めて分かりやすい方で投稿するので、結局、dpの解法を両方とも投稿する。

Wが大きくない場合

• なぜ、「Wが大きくない場合」と前置きしているかというと、この解法の計算量がO(N･W)であり、Wが大きいとTLEになってしまうから。
• 過去の投稿では、ありがちなdp[i][j]による遷移法ではなく、再帰関数をつくって解いていた。今見返してもメチャメチャ分かりづらい。
• 今回は、分かりやすく遷移法のdpで解きます。
• dp[i][w]の意味は、i-1までの荷物について、入れるか入れないか決定済みで、入れた荷物について、重量合計がwとなっているときの価値合計とする。よって、求める解答はdp[N]のときの{w in 0...W}の配列において、最大となるdpの値となる。
• dpの遷移を表すforループは以下の通り

dp[0][W] = 0 // 荷物を選択する前の状態(i=0)では、ナップサックの許容重量(w)はWであり、価値総額(dp)は0となる。
for i in 0..<N {
    for w in 0...W { // wは残りのナップサック容量
        let wv = wvs[i] // (重さ、価値)のタプルの配列wvsから、インデックスiでの値を取得
        
        dp[i+1][w] = dp[i][w] // 全てのケースで遷移可能（荷物をリュックに入れない場合）
        
        if w >= wv.w { // ナップサックの残り残量次第で遷移可能
            dp[i+1][w] = max(dp[i][w - wv.w] + wv.v , dp[i][w]) // 荷物をリュックに入れる場合と、入れない場合で大きい方を選ぶ。
        }     
    }
}
print(dp[N].max()!)

• これなら、理解しやすいでしょ？前回の再帰関数を使った解法は、ちょっと自分でも、思い出して書けるかと言われたら、困るね。というか、確実に書けないね。今回のdpを使った奴なら、書けると思う。
• ちなみに、コード全体は以下の通り。dp典型問題のKnapsack 1に対応してます。

extension Array {
    init(_ cnt: Int, _ v: Element) {
        self = [Element](repeating: v, count: cnt)
    }
    init<T>(_ cnt2:Int, _ cnt1:Int, _ v:T) where Element == [T] {
        self = [[T]](cnt2,[T](cnt1,v))
    }
}

//整数入力
let (N,W) = [readLine()!.split(separator:" ").map{Int($0)!}].map{($0[0],$0[1])}[0]

var wvs:[(w:Int,v:Int)] = [] 
for _ in 0..<N {
    let tpl = [readLine()!.split(separator:" ").map{Int($0)!}].map{($0[0],$0[1])}[0]
    wvs.append(tpl)
}

var dp = [[Int]](N+1,W+1,0)
// dp[i][w]は、i-1番目の荷物まで取捨選択済みで、残り容量wの時の荷物の価値総額

for i in 0..<N {
    for w in 0...W { // wは残りのナップサック容量
        let wv = wvs[i]
        
        dp[i+1][w] = dp[i][w] // 全てのケースで遷移可能
        
        if w >= wv.w { // ナップサックの残り残量次第で遷移可能
            dp[i+1][w] = max(dp[i][w - wv.w] + wv.v , dp[i][w]) 
        }    
        
    }
}

print(dp[N].max()!)

Vが大きくない場合

• Wが大きい場合でも、価値合計Vが大きくない場合は、この解法で解けます。Vが大きくないという縛りがあるのは、この解法の計算量が$O(V･N)$となるためです。
• 当然、遷移法のdpを使いますが、ここでのdp[i][v]の意味は、Wが大きくないときのdp[i][w]と似ています。
• dp[i][w]のときは、荷物をi-1番目まで選択済みで、残り許容重量がwとなるときの、最も大きい価値合計(max関数を利用)でした。元々の題意にも沿った分かりやすいdpです。
• dp[i][v]については、荷物をi-1番目まで選択済みで、価値合計がvとなるときの、最も小さい重量合計、になります。
• dp[i][v]の意味は、題意からは直接結びつきづらいですが、コードの書き方は似ています。

dp[0][0] = 0
for i in 0..<N {
    for v in 0...Vmax {
        let wv = wvs[i]
        
        dp[i+1][v] = dp[i][v] // 全てのケースで遷移可能
        
        if  v - wv.v >= 0 { // 遷移前の状態で「価値合計が負数」はあり得ないので除く
            dp[i+1][v] = min(dp[i][v - wv.v] + wv.w , dp[i+1][v]) // 荷物をリュックに入れる場合と入れない場合で、重量が小さい方を選ぶ。
        }            
    }
}

print(dp[N].enumerated().filter{$0.1 <= W}.map{$0.0}.max()!) 
// 少し分かり辛いけど、enumerated()で(v,w)のタプルを作り、w<=Wの制約下で、vの最大値を求めている。

• Wが大きくないときと、それほど変わらない作りになってるから、あまり悩まないで済むでしょ？
• コード全体は以下の通り。dp典型問題のKnapsack 2に対応してます。

extension Array {･･･} // 省略

//整数入力
let (N,W) = [readLine()!.split(separator:" ").map{Int($0)!}].map{($0[0],$0[1])}[0]

var wvs:[(w:Int,v:Int)] = []
var V = 0 // 各vの合計値

for _ in 0..<N {
    let tpl = [readLine()!.split(separator:" ").map{Int($0)!}].map{($0[0],$0[1])}[0]
    V += tpl.1
    wvs.append(tpl)
}

var dp = [[Int]](N+1,V+1,Int.max / 2)
// dp[i][v]は、i-1番目の荷物まで取捨選択済みで価値総額がvのときの、最小荷物総重量
dp[0][0] = 0

for i in 0..<N {
    for v in 0...V {
        let wv = wvs[i]
        
        dp[i+1][v] = dp[i][v] // 全てのケースで遷移可能
        
        if  v - wv.v >= 0 { // ナップサックの残り残量次第で遷移可能
            dp[i+1][v] = min(dp[i][v - wv.v] + wv.w,dp[i+1][v])
        }    
        
    }
}

print(dp[N].enumerated().filter{$0.1 <= W}.map{$0.0}.max()!) 

• 「Wが大きくないとき」との差は、まず、dpを準備するときの初期値が、0ではなく、Int.max / 2 （十分大きな数値）としているところ。
  • これは、求めるdp（荷物の総重量）は、より小さいものであることを求める流れであるところ、初期値を拒否レート(Wが非常に大きくて、正解から弾かれるようにしておく)にしておいて、dp[0][0]=0から遷移できる条件以外を弾くため。
  • だって、dp[0][v]{v≠0}ってのはあり得ない状況だからね。荷物を何も入れていない(i=0)のに、価値合計vが0以外ってドユコト？って感じでしょ？でも、コードをシンプルにするため、そのようなあり得ない状況をInt.max / 2 とすることで、正解に結びつかないようにしているってこと。

最後に

• dpも典型問題を順に解いていく分には、理解がしやすくて助かるね。最初からこうしておけば良かった。
• でも、アルゴリズムの授業をする教師は楽でいいよね。
  • AtCoderの○○の問題解いとけ！分からなければ、HPの解説読め！それでも沸かないときだけ俺に聞け！
  • コレで十分だもんね。実際、この方法の方が、自分で教えようとする熱心な教師より、生徒の理解が早く実力もついて、生徒のためになる。
  • そのうち、AIの力が伸びれば、人間の教師も要らなくなりそう。
  • 旧帝卒だけど、コレまで「学校の先生のお陰で理解が出来た！ありがとう！」という事が一度もなかったな。自分で本を読んで理解できなかったことは、教師の説明を聞いても理解できなかった。AI登場以前に、日本の教育機関の教師は元から役に立ってないよね。教材が充実してなかった頃は意味があったのかもしれないけど、教材があふれかえってる現代社会で、教師の役割はコーチング（生徒一人一人の学習進捗をみて、それに合わせた指導を行う。その分野の学習に不慣れな生徒に、効率的な学習方法を指導する）くらいしかないと思うけど、そんなことしてる教師は僕の時代にはいなかったしね。僕と同じ時代を過ごした人が教師になって、今は少しはまともになってるのかな？そうだったらいいね。