ナップサックDP問題の種類別要点のメモ

先日以下の記事を利用してナップサックDPの勉強をしていました

この記事はそのとき学んだ問題の種類・相違点についてまとめた内容となります

一定の条件に従ってVを選んだときの最大・最小を選ぶような問題たちのこと

本来は最適化問題というカテゴリに内包される

ナップサック問題ではないがサンプル問題として掲載されていた

本来であればすべての数字を足すだけであるが漸化式として考える場合は、

dp[i+1]= max(d[i] + a[i], d[i])を繰り返せばdp[n]には求めたい合計値が格納される

最大和問題に「Wを超えない範囲で」という制約が加わる

データ構造dpの持ち方が多重配列になるため表を書くとわかりやすい

横軸wで重さの現在値は表現できているのでdpでは

dp[i+1][w]=

W≧w[i]のとき max(d[i][W-w[i]] + a[i], d[i][w])

W<w[i]のとき d[i][w]

N=i, W=wのときに答えとして求めたい値(=価値の総和)を多重配列上で取り出すことを達成するように設計する

そのために、登場しうるNとWの値すべてをindexで指定できるように宣言する

例

dp = [[0] * (W+1) for _ in range(N+1)]

最大和と異なり足し上げることではなく「判定すること」が問われる問題

ナップサックとは以下の点で似ているが、

テーブルの要素がBool型となる点で異なる

部分和問題と異なり「判定した結果の合計」が問われる問題

処理手順などは殆ど同様だが、

テーブルの要素が”結果の合計”となる点で異なり

そのためdpの主要処理がdp[i][j-a[i]] + dp[i][j]となる

部分和問題と異なり「判定した結果に含まれる要素の数」が問われる問題

使用するロジックは殆ど同様だが、

コピー元の値は”十分に大きい値とする”点で異なる

部分和問題と異なり「K個以内の整数という制約」が付与される問題

テーブルの要素を配列として持つ手もあるが計算量がネック

bool値を漸化式で表現することは捨てて

最小個数部分和 × 答えのロジックで代替してもよい

部分和問題と異なり「整数aに利用数mの制限」が付与される問題

従来の処理のなかで、m[i]に基づくループを追加する方針での実装も可能だが計算量がネック

その場合は以下2つの性質を使って、a[i]の余裕(≒余り)を増減させる方針で実装する