DPを使用して利益を最大化しますか？

Question

私はアルゴリズムの問​​題があります。私は解決しようとしましたが、解決策を得ることができませんでした。私はそれがdpを使って解決できるが、ニッチをかなり得ていないことを知っている。 memoization algoを使った再帰的なdpは私には理想的です。小さなヒントやリンクでも可能です。任意の日に、彼は正確にりんごの1を販売している店主が重量の 『n』のリンゴ_私を持っている」

しかし、原因菌に、リンゴはその重みを失うので、店主が稼いでいる：。問題文です。彼は体重のリンゴの日に_私「d」を売る_私は% dの（すなわち、_私 MOD D）の利益。 店主は「

を作ることができる最大の利益は何ですか

入力： 最初の行は「n」、2行目はn個のリンゴの重みを含みます。

例：

入力：

出力：

説明：店主は初日にリンゴ4を販売し、 2日目にリンゴ3。したがって、利益= 4％1 + 3％2 = 1

Answer 1

私によれば、これは2者グラフの最大重量マッチングを使用して解決することができます。

店主はnりんごを持っていて、毎日1 to nから各りんごを割り当てなければなりません。彼はまた、関連するそれぞれの利益を知っています。

したがって、nxnの完全な二部グラフを形成することができ、ハンガリーアルゴリズムを使用して最大の重量一致を得ることができる。