おはやし日記

テーマ……バイク←プログラミング←旅

DP（動的計画法）でナップザック問題を解くまでの過程メモ

DP C++ プログラミング AOJ

0-1 ナップザック問題

この0-1ナップザック問題が解けたので動的計画法初心者がその思考過程を記録しておく。

その後、簡単な書き換えによって一般ナップザック問題（命名: おはやし）が解けたので追記している。

先にコイン問題

前段階としてコイン問題（何種類かのコインでN円払うときの最小支払い枚数を求める）をやった。

動的計画法むずかしい……って人は先にこっち↑を読むと良いかもしれない。保証はしかねるが。

0-1ナップザック問題へ

今回もAOJにお世話になる。提出先は0-1 ナップザック問題である。

問題

容量 $ W $ のナップザックがあり、品物が $ N $ 種類、それぞれ1個ずつある。

品物 $ i (1\le i \le N)$ は、それぞれ価値 $ v_i $ 、重さ $ w_i $ を持っている。重さの合計が容量 $ W $ を超えない範囲で品物をナップザックに入れ、ナップザックに入った品物の価値の合計を最大にしたときその最大値を求めよ

（それぞれの品物について「入れる or 入れない」なので「0-1ナップザック問題」というらしいですhttps://www.morikita.co.jp/data/mkj/081022mkj.pdfのp.88）

制約

  • $1 ≤ N ≤ 100$
  • $1 ≤ v_i, w_i ≤ 1,000$
  • $1 ≤ W ≤ 10,000$

入力

N W
v_1 w_1
v_2 w_2
:
v_N w_N

出力

答えを一行で出力

Ans

DPテーブルの作成

DPなのでDPテーブルを作ります（安直）。DPにもいろいろ種類があるらしいが表を作る方法しか知らないので表を作ります。

この問題、重さあたりの価値 $ v_i/w_i $ が大きい方から詰めればいいと思いきや、一般にはそれではダメだそうです。よってDP。

また入力例1をこねくり回してみます。入力例1は

4 5
4 2
5 2
2 1
8 3

ナップザック容量 $ W=5 $ 、品物数 $N=4$ 、 $ (v,w) = \{(4,2), (5,2), (2,1), (8,3) \} $

とりあえずこんな表を用意してみた。v, w の下に並ぶのがそれぞれの品物の価値と重さ。

i↓ j→ 0 1 2 3 4 5
0 v w 0 0 0 0 0 0
1 4 2 0
2 5 2 0
3 2 1 0
4 8 3 0

$$ dp[i][j] := i番目の品物\dot{ま}\dot{で}使って重さjに収めたときの最大価値 $$

とする。最大値を求めるので表の全部を0初期化して良いのだが、見にくくなるので端っこだけ0埋め。

架空の品物0ではナップザックに「価値」が入らないので $ i=0 \Rightarrow dp[i][j] = 0 $ 。容量0でも「価値」が入らないので $ j=0 \Rightarrow dp[i][j] = 0 $ 。

なんとなく埋めてみる。一回間違った発想をしてしまったがそれは後ほど。今は正答ルートで行く。

i↓ j→ 0 1 2 3 4 5
0 v w 0 0 0 0 0 0
1 4 2 0 0 4 4
2 5 2 0 0 5 5
3 2 1 0 2 5 7
4 8 3 0 2 5 8
  • 容量1のとき、品物2までしか使えないと何も入れられず、品物3が解禁されると $ (v_3, w_3) = (2,1) $ を入れて価値が2入る。
  • 容量2のとき、品物1までのときは価値4が入る。品物2を解禁すると価値5が入る。
  • 容量3のとき、品物1までのときは価値4、品物2までのときは価値5、品物3までのときは品物2,3を入れて合計価値7、品物4までのときは品物4を入れて価値8。

残りすくないので全部埋めてしまおう

i↓ j→ 0 1 2 3 4 5
0 v w 0 0 0 0 0 0
1 4 2 0 0 4 4 4 4
2 5 2 0 0 5 5 9↘︎ 9↓
3 2 1 0 2 5 7 9 11
4 8 3 0 2 5 8 10 13

これとにらめっこしつつ、前回を思い出しつつ、漸化式を考える。

たとえばdp[3][5]だが、品物3を使わないときは品物2まで使った最適の詰め方dp[2][5] = 9を採用する。一方品物3を使うとすると、「重さ制限$4(=5-w_3)$として品物2までで最適に詰めたナップザックに品物3を追加して容量5に合わせる」のが価値を最大にする方法で、すなわちdp[2][4]+v[3] = 9+2 = 11となる。実際価値が多く入るのは品物3を使ったほうだから、両者の最大値をとって

$$ dp[3][5] = \max(dp[2][5], dp[2][5-w_3]+v[3]) = \max(9, 9+2) = 11 $$

という式でdp[3][5]は導かれる。（雑な言語化：wは右に進行する大きさでvは加算する数）下に、クソダサい図を載せる。左右の入れ方で、どっちの方が中身の価値を大きくできるかという話。

f:id:o-treetree:20200524175748p:plain

ここで品物4のことを考えてはいけない。今はあくまでも品物3までが選択肢なのだ。品物4は、品物3までの表を一通り埋めた後にしゃしゃり出てきた品物（？？？）と考えて良い。

なんとなくわかった気がするので漸化式を書く。今回も、表の「左のほう」を参照できるのは $ j \ge w_i $ のときに限ることに注意して

\begin{align} dp[i][j] = \begin{cases} \min (dp[i-1][j], dp[i-1][j-w_i]+v_i) & (j \ge w_i) \cr dp[i-1][j] & (otherwise) \end{cases} \end{align}

となる。dpの定義を再掲して

$$ dp[i][j] := i番目の品物\dot{ま}\dot{で}使って重さjに収めたときの最大価値 $$

であるので求めたいものは

\begin{align} N番目の品物まで使って重さWに収めたときの最大価値 &= dp[N][W]\cr &= dp[4][5]\cr &= 13 \end{align}

である。ちなみに品物の入れ方は $\{ 2,4 \} \Rightarrow (v,w) = (5+8, 2+3) = (13, 5)$

実装

#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;

int main(){
  int N,W;
  cin>>N>>W;
  vi v(N+1), w(N+1); //価値v 重さw
  for(int i=1; i<=N; i++){
    cin>>v[i]>>w[i];
  }

  vvi dp(N+1, vi(W+1, 0)); //品物iまでで重さj以内で収める時の価値の最大値

  for(int i=1; i<=N; i++){
    for(int j=1; j<=W; j++){
      if(j>=w[i]){
        dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+v[i]);
      }else{
        dp[i][j] = dp[i-1][j];
      }
    }
  }

  int ans = dp[N][W];

  cout<<ans<<endl;
}

0-1 ナップザック問題でAC確認済み（メモリ消費 6828 KB）。

これも1次元DPにできる

敢えてするほどでもないが、できるので紹介。

漸化式などを考えると、$dp[i][j]$ を求めるのに必要な表の範囲は $ [0, i-1] , [0, j] $。前回は $i,j$ 共に昇順でループを回していたが、今回はできるだけdp[i-1]を生かしておかなければいけないので、$i$ 昇順 $j$ 降順で回す。

#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;

int main(){
  int N,W;
  cin>>N>>W;

  vi v(N+1), w(N+1);
  for(int i=1;i<=N;i++)cin>>v[i]>>w[i];

  vi dp(W+1, 0);

  for(int i=1; i<=N; i++){
    for(int j=W; j>=1; j--){ //j後ろから
      if(j>=w[i]){
        dp[j] = max(dp[j], dp[j-w[i]]+v[i]);
      }
    }
  }
  cout<<dp[W]<<endl;
}

AC確認済み（メモリ消費 3116 KB）

途中でつまづいた部分、そして一般ナップザック問題へ

途中、ちょっと間違った見方をしていたのでこんがらがり、参考に載せたサイトをカンニングしてしまいました。その間違いをざっと紹介。

間違ったDPテーブル

i↓ j→ 0 1 2 3 4 5 6
0 v w 0 0 0 0 0 0 0
1 4 2 0 0 4 4 8 8 12
2 5 2 0 0 5 5 10 10 15
3 2 1 0 2 5 7 10 12 15
4 8 3 0 2 5

同じ品物を何回も使えると思ってしまった。

それはさておき、AOJでは0-1 ナップザック問題の後にナップザック問題が用意されている。これは、0-1ナップザック問題で各種1つしかなかった品物が、それぞれ無限に用意されている、つまり同じ品物を何個も入れて良い、というもの。

巷でいう（？）ナップザック問題は0-1ナップザック問題を指していることが多いような気がしたので、品物の重複を許す方を一般ナップザック問題と呼ぶこととした。

話は戻って先ほどの「間違ったDPテーブル」だが、これは一般ナップザック問題に対するDPテーブルになっている。なぜなら「同じ品物を何回も使える」としているからだ。

漸化式は、「表の左側を見るとき $i-1$ の列ではなく $i$ の列を見る」ということに気をつけて

\begin{align} dp[i][j] = \begin{cases} \min (dp[i-1][j], dp[i][j-w_i]+v_i) & (j \ge w_i) \cr dp[i-1][j] & (otherwise) \end{cases} \end{align}

minの引数2つ目のところが違う。実装も、ここの書き換えのみで一般ナップザック問題に適用できる。

1次元DPにするときは、漸化式はそのままで、jのループを前から回すようにすれば、書き換え済みのdp[j-w[i]]を参照できる。

//一般ナップザック問題
  for(int i=1; i<=N; i++){
    for(int j=1; j<=W; j++){ //j前から
      if(j>=w[i]){
        dp[j] = max(dp[j], dp[j-w[i]]+v[i]);
      }
    }
  }

おしまい

あの（？）有名な（？）ナップザック問題が解けてよかったですね！！！おしまい。

参考

プライバシーポリシー ・お問い合わせはこちら