ナップサックの諸相 - 早稲田大学チームvivid_turtle 知見共有@ ウィキ

動的計画法の適用の典型としてナップサック問題が挙げられる。Nこの荷物にそれぞれ質量W_i, 価値V_iがあり、それらを質量W_max以下の条件で、いかにして価値を最大化するというおなじみのものである。
この時、重さあたりの価値の高い順に選択するのは嘘解法であり、基本的に全探索をベースとして考えないといけない。
ナップサック問題には多数のバリエーションがあり、蟻本やAOJや有志ブログ記事に大量にあるので、ここでは割愛する。
ここでは、ナップサックに帰着できるような問題パターンをあげる。

以下の文章内でのナップサック用語について解説する。

0-1ナップサック

1種類のアイテムは1回しか使えない。

個数無制限ナップサック

1種類のアイテムは何度でも使える。

有限個ナップサック

1種類のアイテムは決められた回数まで使える

以下例題を示す。

Diverta2 - D(600)

https://atcoder.jp/contests/diverta2019-2/tasks/diverta2019_2_d

この問題は、条件を整理すると、
市場A->市場B　の交換
と
市場B->市場A　の交換
の二つを行っていて、どんぐりの数を最大化するというものである。

ここで、市場Aで x個/金属H1単位 のものを市場Bで y個/金属H1単位 で交換する場合を考える。操作としては
x個のどんぐりを払って、y個のどんぐりを手に入れる。ただし、この操作は所持してるどんぐりの数が許す限り、何回行ってもよい。
となる。
これこそが定石なのであるが、こういうたかだか定数個(問題文の設定で定数個になってる場合が多い)しかない、一定のリソース内での交換はつぎのようにナップサック問題に帰着できる場合が多い。
実際この問題はこのように設定すればよい。
初期の所持どんぐりの数はW_max。x個/単位->y個/単位の交換手段はW_i = x, V_i = y。
このように置換すれば、交換手段に回数制限はないため、個数無制限ナップサックに帰着することができた。

なおdp[i][j] := i番目の品物まで見て質量jのときの価値の最大値として定義した場合、実際の得られるどんぐりの量はdp[i][j] + (N - j)と交換することなく余っていたN - jこのどんぐりの数も足す必要がある(一敗)。

また、この問題は、A->BもB->Aも本質的には同じ回数無制限ナップサックなので、二回のDPをすればよい。しかし、一回目のW_maxはどんぐりの数Nであるが、二回目は一回目の置換での得られた最大のどんぐりの数がW_maxである(二回目の交換では一回目の置換でのどんぐりの数の最大値まで使えるため)。