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

はじめに

• AtCoderのABC(AtCoder Beginner Contest)のA,B,C,D問題は、時間を掛ければフィーリングで解くことが出来るようになってきたけど、ABC358のE問題の解説動画を見て、E問題以降は特別な知識がないと解けそうもないと思い、とりあえず、初めて聞いた用語であるDP法のナップサック問題の解法を脳味噌に刻み込むことにした。
• ナップサック問題とは、下図のような許容重量15kgまでのナップサックにいれらる荷物の最大価値（下図はドルベース）を算出するものである。なんとなく、1kg当たり価値の高い順に荷物を選べば良い気もするけど、そこまで単純ではないので、解法が研究されている。
  
• 当然、全ての組み合わせを考慮すれば求めることは出来る。でも、n個の荷物の場合は$2^n$のケース（bit全探索¹）を処理することとなり、AtCoderでは概ね$10^8$回の計算までしか出来ないから、nは26個程度で限界となる。よって、AtCoderでnが30を超えるようなナップサック問題が出たときには、DP法を用いて解く必要がある。

問題例

• 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全探索では部分点すら取れない。

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個の数列だとタイムアウトした。

// 単純な再帰関数
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個の数列表示
}

• 動的計画法（ボトムアップ方式)は、直感的な方法。コードを見て貰えば一目瞭然。50個の配列だけど、コードテストでの時間は2msとなり、桁違いに速くなった。まぁ、最初からフィボナッチ数列を作るだけなら、こっちのボトムアップ方式の方を思いつくよね。ちなみに、「n-1」までの計算結果を配列fbsに記憶して「n」の計算に使用しているけど、この計算結果を後工程で使うために記憶することを「メモ化」と呼ぶらしい。ちなみに、ボトムアップ方式は次の 動的計画法（トップダウン方式） の前振りだから、もう少しお付き合いください。

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)}

• 動的計画法（トップダウン方式)が、動的計画法の真打ちです。再帰関数とメモ化をミックスするやり方だけど、詳しくは次のコードを見てね。

//　最初に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〜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を入れない*/ )

• 上記の考え方を元にコードを書くと、以下の通り

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問題は、ABCの問題Dといっても、当時は問題Ａ〜Ｄしかなかった時代だから、単純なナップサック問題じゃないのかも。
• もっと、修行します。

1. bit全探索についての詳細は、APG4bの「AC3.05.ビット演算」を見て貰えればと思うけど、簡単に説明すれば、選択する/選択しないの２択できる事柄が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全探索を使って解く下腿の問題をよく見ると思う。 ↩