ナップサック問題の解き方【競技プログラミング対応 - swiftでの解法】

# はじめに
- AtCoderのABC(AtCoder Beginner Contest)のA,B,C,D問題は、時間を掛ければフィーリングで解くことが出来るようになってきたけど、[ABC358のE問題の解説動画](https://www.youtube.com/live/Uxd2qSY6KDo?feature=shared)を見て、E問題以降は特別な知識がないと解けそうもないと思い、とりあえず、初めて聞いた用語である[DP法](https://ja.wikipedia.org/wiki/%E5%8B%95%E7%9A%84%E8%A8%88%E7%94%BB%E6%B3%95)の[ナップサック問題](https://ja.wikipedia.org/wiki/%E3%83%8A%E3%83%83%E3%83%97%E3%82%B5%E3%83%83%E3%82%AF%E5%95%8F%E9%A1%8C)の解法を脳味噌に刻み込むことにした。
- ナップサック問題とは、下図のような許容重量15kgまでのナップサックにいれらる荷物の最大価値（下図はドルベース）を算出するものである。なんとなく、1kg当たり価値の高い順に荷物を選べば良い気もするけど、そこまで単純ではないので、解法が研究されている。
![wikipedia画像](https://upload.wikimedia.org/wikipedia/commons/thumb/f/fd/Knapsack.svg/440px-Knapsack.svg.png)
- 当然、全ての組み合わせを考慮すれば求めることは出来る。でも、n個の荷物の場合は$2^n$のケース（bit全探索[^1]）を処理することとなり、AtCoderでは概ね$10^8$回の計算までしか出来ないから、nは26個程度で限界となる。よって、AtCoderでnが30を超えるようなナップサック問題が出たときには、DP法を用いて解く必要がある。
[^1]:bit全探索についての詳細は、APG4bの「[AC3.05.ビット演算](https://atcoder.jp/contests/apg4b/tasks/APG4b_ac?lang=ja)」を見て貰えればと思うけど、簡単に説明すれば、選択する/選択しないの２択できる事柄がn個あるとき、全体の選択パターン$2^n$を総当たりで行う方法のこと。
プログラムでは、そのフラグ管理を２進数で行うので、bit全探索と呼ぶらしい。例えば、7個の2択のとき、全部選択するパターンを0b1111111(=$2^7-1$)、全て選択しないパターンを0b0000000(=$0$)、最初の1つのみを選択するパターンを0b0000001とすれば、最初の2つを選択するパターンは0b0000011、最後の3つを選択するパターンは0b1110000となる。
全てのパターンを試すには、`for i in 0..<(1<<7) {処理の内容}` の形でコードを書くこととなる。なお、この「1<<7」は$2^7$のこと。swiftは整数の累乗計算として「2^7」と言う書き方が出来ないため、bit演算子「<<」（左シフト）を使うのが楽。
AtCoderでは、nが20未満で、bit全探索を使って解く下腿の問題をよく見ると思う。

# 問題例
- [ABC032のD問題](https://atcoder.jp/contests/abc032/tasks/abc032_d)で文字通りナップサック問題が出題されているので、これを対象とする。
- 入力例１は下記の通り、このときの答えは、16(荷物 ②+③)。なお、本問の個数Ｎについて、1≦N≦200の制約となっていることから、bit全探索では入力例1は解けても、Ｎが30ぐらいからはタイムアウトにより解けなくなる。
```
3 10 // 荷物3個、許容重量10
15 9 // 荷物① 価値15、重量9
10 6 // 荷物② 価値10、重量6
6 4  // 荷物③ 価値 6、重量4
```


# bit全探索（ナップサック問題）
- まずは、総当たりのbit全探索での解法を書く。計算量はO($2^N$)となる。ABC032のD問題では、入力例1〜入力例4が示されていて、入力例2はN=30のためタイムアウトとなるけど、その他の入力例のNは10以下なので解ける。ただし、ABC032のD問題は、部分点ですらN=30の場合を解けないとアウトなので、bit全探索では部分点すら取れない。
```swift
let (N,W) = [readLine()!.split(separator:" ").map{Int($0)!}].map{($0[0],$0[1])}[0]

var vws:[[Int]] = [] // valueとweightの組み合わせの配列なので、配列名をvwsとした。
for _ in 0..<N {
    vws.append(readLine()!.split(separator:" ").map{Int($0)!})
}

var maxv:Int = 0 // 解答となるvalueの最大値

for bitFlag in 0..<(1<<N) { // bit全探索のフラグ管理だから、名称をbitFlagとした。
    var v:Int = 0
    var w:Int = 0
    for i in 0..<N {
        if bitFlag >> i & 1 == 1 { // 全探索フラグのiビット目が立ってる場合
            v += vws[i][0]
            w += vws[i][1]
        }
    }
    if w <= W { // 条件を満たすときのみ、最大値チェックを行う
        maxv = max(maxv , v)
    }
}

print(maxv)
```

# 動的計画法(dp：dynamic programming)の紹介【フィボナッチ数列】
- bit全探索の計算量O($2^N$)に対し、dpの計算量はO($N･Ｗ$)とのこと。このWはナップサックの許容重量。例えば、各荷物の重さが整数値で表されるときのWを指す。もし、各荷物の重さが10単位刻みなら、計算量は10分のⅠになり、重さが0.1単位刻みなら、計算量は10倍になる。なお、Nが十分大きければ、$O(2^N)>O(N･Ｗ)$となる。
- 動的計画法の分かり易い例として、フィボナッチ数列の算出がある。
- フィボナッチ数列とは、$f(n) = f(n-1) + f(n-2)$ （$f(0)=0,f(1)=1$）となるような数列のことを指す。
- これは、n=0から初めて順にf(n)を算出すれば、nが巨大な数値になっても簡単に算出できるが、再帰関数を用いて計算すると、$O(2^n)$の計算量となるため、nが大きくなるとタイムアウトにより計算が終了できなくなる。AtCoderのコードテストをつかうと、40個の数列だと0.9秒、45個だと9.8秒で終了できたが、50個の数列だとタイムアウトした。
```swift
// 単純な再帰関数
func fib(_ n:Int)->Int{
    switch n {
        case 0:
            return 0
        case 1:
            return 1
        default:
            return fib(n-1) + fib(n-2) // nが増えると、計算量が倍々で増えていく。
    }
}

for i in 0..<40{
 print(i,fib(i)) //40個の数列表示
}
```
- 動的計画法（ボトムアップ方式)[^2]は、直感的な方法。コードを見て貰えば一目瞭然。50個の配列だけど、コードテストでの時間は2msとなり、桁違いに速くなった。まぁ、最初からフィボナッチ数列を作るだけなら、こっちのボトムアップ方式の方を思いつくよね。ちなみに、「n-1」までの計算結果を配列fbsに記憶して「n」の計算に使用しているけど、この計算結果を後工程で使うために記憶することを「メモ化」と呼ぶらしい。ちなみに、ボトムアップ方式は次の __動的計画法（トップダウン方式）__ の前振りだから、もう少しお付き合いください。
[^2]:ボトムアップ方式：メモ化する配列をdpとして、欲しい解答がdp[N]のとき、dp[0]から順に1つずつ埋めていく方式。
```swift
func fibs(_ n:Int)->[Int]{
    var fbs:[Int]=[]
    var fb:Int = 0
    
    for cnt in 0..<n {
        switch cnt {
            case 0:
                fb = 0
            case 1:
                fb = 1
            default:
                fb = fbs[cnt - 2] + fbs[cnt - 1]
        }
        fbs.append(fb)
    } 
    return fbs
}

fibs(50).enumerated().map{print($0.0,$0.1)}
```
- 動的計画法（トップダウン方式)[^3]が、動的計画法の真打ちです。再帰関数とメモ化をミックスするやり方だけど、詳しくは次のコードを見てね。
[^3]:トップダウン方式：メモ化する配列をdpとして、欲しい解答がdp[N]のとき、コード的に最初にdp[N]を求めようとするけど、具体的なdpの数値自体は再帰関数によりdp[i](i≠N)から先に求める方法。なお、欲しい解答がdp[0]のときは、dp[i](i≠0)から先に値を算出することとなる。
```swift
//　最初にMAX個の箱を用意しておく
let MAX:Int = 93
var mems = [Bool](repeating: false, count: MAX)
var fibs = [Int](repeating: 0, count: MAX)

// フィボナッチ数列の最初の2項を格納しておく
(fibs[0],fibs[1]) = (0,1)
(mems[0],mems[1]) = (true,true)

// 過去に算出済みの場合は計算をサボる
func fib(_ n:Int)->Int{
    var fb:Int = 0
    if(!mems[n]) {
        fb = fib(n-1) + fib(n-2)
        fibs[n] = fb
        mems[n] = true
    } else {
        fb = fibs[n]
    }
    return fb
}

// 計算①
// for i in 0..<MAX{
// print(i,fib(i))
// }

// 計算②
print(MAX-1,fib(MAX-1)) // 92 7540113804746346429(7.5e18)
```
- 上記コードでコメントアウトしている計算①であれば、「ボトムアップ方式」と実質的に同じことになるが、計算②でもコードテストの実行時間は2secとなった。
- なお、フィボナッチ数列の93個目の数値f(92)は7.5e18となり、64bit環境のInt上限9.0e18ギリギリの値となるので、上記コードではMAX=93としている。

# 動的計画法（ナップサック問題）
- ナップサック問題を、前記の「トップダウン方式」を使って解く。そもそも、競技プログラミングで動的計画法を使うような問題は「ボトムアップ方式」で簡単に解けるようなパターンが無いのが普通と思われる。
- まず、経過途中を表す表現を決める。例えば、全部で30個の荷物があり、全てに番号(0-29)が振られてるものとし、既に番号0〜12までの荷物のうち、何をナップサックに入れるかきめてあるものとする。
- このとき、ナップサックの許容重量が100であるところ、既にナップサックには合計重量40の荷物が入っているとき、のこりの荷物の先頭番号は13となり、ナップサックの残りの許容重量は60となるので、この状況を（13,60）と表現する。
- この表現法によれば、ナップサックに何も入れてないときは、(0,100)となる。
- こう考えると、番号0の荷物の重さが7だったとき、(1,??)の状態としては、(1,93)か(1,100)の2種類ある。
- 初期状態(0,100)より、ナップサック問題の解答をans(0,100)と表現すれば、下記のように書ける。
```
ans(0,100) = max( ans(1,93) + value(0) /*荷物0を入れる*/  ,  ans(1,100) /*荷物0を入れない*/ )
```
- 上記の考え方を元に再帰関数ansを使ってコードを書くと、以下の通り
```swift
let (N,W) = [readLine()!.split(separator:" ").map{Int($0)!}].map{($0[0],$0[1])}[0]

var vws:[[Int]] = []
for _ in 0..<N {
    vws.append(readLine()!.split(separator:" ").map{Int($0)!})
}

let nils = [Int?](repeating:nil,count:W+1) // 不要な0がある分だけ個数を増やした。
var anss = [[Int?]](repeating:nils,count:N)
var cnt_n = 0 //新規計算
var cnt_r = 0 //再利用

func ans(_ i:Int,_ W1:Int)->Int{
    
    var v = vws[i][0]
    var w = vws[i][1]
        
    if let ret = anss[i][W1] {
        cnt_r += 1
        return ret
    } 
    
    var ret = 0
    if(i < N - 1)  {
        ret = max(/*n0を入れる*/w <= W1 ? ans(i+1,W1-w) + v : 0,/*n0を入れない*/ans(i+1,W1))
    } else {
        ret = (w <= W1 ? v : 0)
    }
    anss[i][W1] = ret
    cnt_n += 1
    return ret
}

print(ans(0,W))
print("計算回数：\(cnt_n)")
print("再利用回数：\(cnt_r)")
```
- 下記の入力例3の場合、結果は「3657162058」となり、計算回数：892、再利用回数：32となり、3msで終了した。せっかく、dpを使ったのに、再利用数が少なくて泣ける。
```
10 2921
981421680 325
515936168 845
17309336 371
788067075 112
104855562 96
494541604 960
32007355 161
772339969 581
55112800 248
98577050 22
```
- また、Wが巨大となるような入力例4の場合は、Nは10と小さいのに、Wが9.3e8と大きいために`let nils = [Int?](repeating:nil,count:W+1)`が生成出来ずエラーとなってしまった。うーむ、別のロジックが必要そうだね。
```
10 936447862
854 810169801
691 957981784
294 687140254
333 932608409
832 42367415
642 727293784
139 870916042
101 685539955
853 243593312
369 977358410
```
- 今回はこれでギブアップ．．．

# おわりに
- よくよく見たら、ナップサック問題の例とした[ABC032のD問題](https://atcoder.jp/contests/abc032/tasks/abc032_d)は、ABCの問題Dといっても、当時は問題Ａ〜Ｄしかなかった時代だから、単純なナップサック問題じゃないのかも。
- もっと、修行します。

【追記】修行の結果は、下記

https://qiita.com/kei_tnk/items/00b573ac7c9c853f3939