0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

動的計画法での配列使い回しのイメージ

Posted at

はじめに

0-1ナップサック問題での配列使い回し

  • ナップサック問題でdp配列を使い回すことを考える
  • 各商品を高々1個までしか入れられないとき、更新後の値を読まないように工夫する必要がある
    • weightの逆順に読むか
    • 2個の配列を使いまわすか
  • イメージ
    Screenshot at 2021-12-23 22-05-12.png

0-N ナップサック問題での配列使い回し

  • 各商品を2個以上入れられるとき、更新後の値を読む必要がある
  • イメージ
    Screenshot at 2021-12-23 22-34-49.png
0
0
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
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?