Go to Qiita Advent Calendar 2024 Top
LoginSignup
0
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@kei_tnk

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

Last updated at Posted at 2024-06-16

はじめに

  • AtCoderのABC(AtCoder Beginner Contest)のA,B,C,D問題は、時間を掛ければフィーリングで解くことが出来るようになってきたけど、ABC358のE問題の解説動画を見て、E問題以降は特別な知識がないと解けそうもないと思い、とりあえず、初めて聞いた用語であるDP法のナップサック問題の解法を脳味噌に刻み込むことにした。
  • ナップサック問題とは、下図のような許容重量15kgまでのナップサックにいれらる荷物の最大価値（下図はドルベース）を算出するものである。なんとなく、1kg当たり価値の高い順に荷物を選べば良い気もするけど、そこまで単純ではないので、解法が研究されている。
    wikipedia画像
  • 当然、全ての組み合わせを考慮すれば求めることは出来る。でも、n個の荷物の場合は$2^n$のケース（bit全探索1）を処理することとなり、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個の数列表示
}
  • 動的計画法（ボトムアップ方式)2は、直感的な方法。コードを見て貰えば一目瞭然。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)}
  • 動的計画法（トップダウン方式)3が、動的計画法の真打ちです。再帰関数とメモ化をミックスするやり方だけど、詳しくは次のコードを見てね。
//　最初に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を使ってコードを書くと、以下の通り
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全探索を使って解く下腿の問題をよく見ると思う。 ↩

  2. ボトムアップ方式：メモ化する配列をdpとして、欲しい解答がdp[N]のとき、dp[0]から順に1つずつ埋めていく方式。 ↩

  3. トップダウン方式：メモ化する配列をdpとして、欲しい解答がdp[N]のとき、コード的に最初にdp[N]を求めようとするけど、具体的なdpの数値自体は再帰関数によりdpiから先に求める方法。なお、欲しい解答がdp[0]のときは、dpiから先に値を算出することとなる。 ↩

0
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?