No.527 ナップサック容量問題 (0-1ナップサック)

Quiz

https://yukicoder.me/problems/no/527

Submit

https://yukicoder.me/submissions/342051

解法

  • 普通にナップサック問題を解く
  • dp[i][j]
    • i : i番目に着目
    • j : 残りの容量
    • その時の最大の価値
  • dpテーブルを埋めた後、dp[0][各重み] == Vなる重みをリストアップ
  • そのリストのmax, minが答え
  • min==0のときは、1を返すようにする (容量は1以上と設定されている)
  • max>100000のときは、infを返すようにする

その他

参考(メモ化再帰のナップサック)

http://dai1741.github.io/maximum-algo-2012/docs/dynamic-programming/