AOJ 0042 A Thief

はむこの解答 問題概要 罠 ・ 勉強したこと ・ 方針 ただのナップサック問題。だったので、紙を使わずに暗算で漸化式を立てて解きました。 dp[j][i] = i個目までの美術品をjの重さで盗んだ時の価値の最大値 初期状態は、dp[j][0] = 0 for all j 漸化式は、dp[j][i] = max(dp[j][i], dp[j-w][i]))で更新。