Q&A
Mはどれくらいの大きさなのですか？
（大きさによっては簡略化できることが考えられます）
Pythonの初学者です。（Python3.7を使っています）
全探索すれば答えが出せる問題ですが、すぐに計算時間が発散してしまいます。これを避ける方法について教えてください。
最初にM（整数）というお金を持っているとします。P（整数値）％という金利が与えられますが、Pをばらばらにして複利にして使うことができます。
ただし、金利は一度計算した時点で、小数点以下は切り捨てられます。
例として、M=1000, P＝3％のとき、以下の4通りのうち、最大値を求めたいです。
① int(int(int(M*(100＋P)/100)・(100＋P)/100))・(100＋P)/100))
② int(int(M*(100＋P)/100))・(100＋2P)/100))
③ int(int(M*(100＋2P)/100))・(100＋P)/100))
④ int(M*(100＋3P)/100))
可能なすべての組み合わせを求めて、それらの最大値を計算すればよいのですが、P=20くらいで計算時間が1秒を超えてあとは発散してしまいます。できれば、P=100%まで計算できるようにしたいです。
P=20の場合の全探索の一部を書き出してみると、最大値を与える組み合わせはかなり多く規則性は見えませんが、少ない数（1～10）の組み合わせで最大値を実現している組み合わせが見られます。それで、一つの可能性として、Pを10個の単位に分割してして、10個単位で最大値を与える組み合わせをつないでいくというアルゴリズムでトライしましたが、全探索の結果と比較するとうまくいきません。（10個がよいのか11個がよいのか、いろいろトライしましたが）
どのようなアルゴリズムで考えればよいか教えていただければ幸いです。
Mは、１円から100万円くらいまでのイメージです。
よろしくお願いします。
些細なことですが、切り捨て除算子 // を使うと整数型を保ったまま切り捨てで除算ができます。
毎回int呼び出すのは見づらいでしょう。
ご指摘ありがとうございます。
回答1件
0
ベストアンサー
1%ずつ進める動的計画法を取ってはどうでしょうか。
- 1%だけのとき…1通りしかない
- 2%のとき…スタートから2%使ったときと、1%+1%としたときの大きな方
- 3%のとき…スタートから2%使ったとき、1%+2%のとき、2%での結果+1%の3つを比較しての最大値
このように進めていけば、O(P**2)で片付きます。
投稿2021/10/28 01:54
総合スコア146018
1%だけのとき…1通りしかない
2%のとき…スタートから2%使ったときと、1%+1%としたときの大きな方
3%のとき…スタートから＜3＞%使ったとき、1%+2%のとき、2%での結果+1%の3つを比較しての最大値
4%のとき…スタートから4%使ったとき、1%+3%のとき、3%での結果+1%の3つを比較しての最大値
という理解でよろしいでしょうか？（不勉強ですみません）
4%のときは、2%での結果＋2%のときも必要です。
ありがとうございました。実装して非常に高速であることが確認できました。動的計画法については、少し時間をかけて勉強します。
あなたの回答
tips
プレビュー
