読者です 読者をやめる 読者になる 読者になる

ぷよぐやみんぐ日記

@nemu_souがお送りするNIT-Ok ict委員会でのぷよぐやみんぐ日記 雑記

0-1 ナップザック問題のDPを考える

「0-1 ナップザック問題」

AOJ (0-1 Knapsack Problem | Aizu Online Judge

↑これ 

問題内容は以下の通り

価値が vi 重さが wi であるような N 個の品物と、容量が W のナップザックがあります。次の条件を満たすように、品物を選んでナップザックに入れます:

  • 選んだ品物の価値の合計をできるだけ高くする。
  • 選んだ品物の重さの総和は W を超えない。

価値の合計の最大値を求めてください。

DP(Dynamic Programming)、もしくは動的計画法と呼ばれる解き方(考え方)の入門的な問題(かな?)

そもそもDPってなに?

大雑把に考えて、一度見たものを記録(配列に保存する等)してあとで必要になった時にべんり~。みたいなもの

それの何がいいの?

ひとつの情報を扱うときに保存することで何度も計算したりしなくてよくなる。

計算時間が減る

いままで手に負えなかった一部のTLE(Time Limit error)に対応できるようになる。

わーい、やったー(/・ω・)/

 

考え方が...

そう、べんり。わかる。

ただ、ぼくじゃちょっと難しい。

だから考えたことを残しておく事にした。

ここからがアレ

 じゃあ何が難しいなあと感じたのか

動的計画法を使う(使わなくても簡単にできる)問題にフィボナッチ数列の問題がある

AOJ(フィボナッチ数列 | アルゴリズムとデータ構造 | Aizu Online Judge

int fib(unsigned int n) {
    int memo[1000] = {0, 1}, i;
    for (i = 2; i <= n; i++) {
        memo[i] = memo[i - 1] + memo[i - 2];
    }
    return memo[n];
}

(コードはwikiのだからそのまま使ってもできないと思うまる)

わかる

 

さあテーマの0-1 ナップザック問題。(問題内容は上見て思い出して)

#include <iostream>
 
using namespace std;
 
int dp[101][10001];
int main()
{
  int N, W, i, j, ans = 0;
  cin >> N >> W;
  int v[N + 1], w[N + 1];
 
  for (i = 0; i < N; i++){
    cin >> v[i] >> w[i];
  }
  for (i = 0; i < N; i++){
    for (j = 0; j <= W; j++){
      dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);
    }
    for (j = 0; j <= W; j++){
      if (j + w[i] <= W){
        dp[i + 1][j + w[i]] = max(dp[i + 1][j + w[i]], dp[i][j] + v[i]);
      }
    }
  }
  for (i = 0; i <= W; i++){
    ans = max(ans, dp[N][i]);
  }
  cout << ans << endl;
 
  return (0);
}

ぼくがNIT-Okで所属しているICT委員会のslackの1day1probrem channelで問題として出されたとき上のコードを提出しました。
しかしこの問題、以前に一度挑戦してあきらめ他の人の解答を見てなるほど~。は~。わからん。とか言ってたんです。
そして今回解いたとき「こんな感じだったなー」、「こうだったかなー」と記憶を頼りにやってました。

そうじゃないんだ!!!

それじゃ使えてるとは言えないんだ!!!

ばかやろう!!!!!!!!!!

めっちゃ分かってなかった場所がここ

dp[i + 1][j + w[i]] = max(dp[i + 1][j + w[i]], dp[i][j] + v[i]);

...(。´・ω・)???
てな感じですよ

やっとここから

今回書いておきたかったことはここから始まる.
ただの整理である.

for (i = 0; i < N; i++){
  for (j = 0; j <= W; j++){
    dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);
  }
  for (j = 0; j <= W; j++){
    if (j + w[i] <= W){
      dp[i + 1][j + w[i]] = max(dp[i + 1][j + w[i]], dp[i][j] + v[i]);
    }
  }
}
  • 一番外側のfor文はi=0からN-1まで、つまり個数分roop.
  • 内側の一つ目のfor文で個数違いで同じ重さのとき高い方の価値で上書きしている.
  • 内側の二つ目のfor文で「i番目のものをナップザックに入れたときの重さ<=ナップザックに入る重さ(W) 」が真のとき.
  • max(前に保存された価値, i番目のものを入れたときの価値)で大きい方を保存.

最終的にdp[N][0≦j≦W]の高さに全ての個数を見た後の重さ違いの価値の最大値が入っている.

for (i = 0; i <= W; i++){
  ans = max(ans, dp[N][i]);
}
cout << ans << endl;
  • 最後にその中で一番価値が高い値を変数ansに保存して出力.

いやーわかりやすいなあ(((棒)))

終わりです。

なんか今後もわかんないことがあればこんな感じで一回ちゃんとまとめていこうかと思います.

それでは。