質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

88.58%

Pythonの組み合わせ最適化について

受付中

回答 6

投稿

  • 評価
  • クリップ 3
  • VIEW 1,700

babbleman

score 39

ポイントが10あるとします
あるものの価値が、1ポイントを使うことによって
A(後)=A(前)×(100+p)/100(小数点以下切り捨て)にグレードアップできるとします。
ここでAはその物の価値、pはポイントです。
この時Aを最大にするにはどのようにポイントを使っていけば良いか、という問題ですが
私がこれを解こうとした時に考えた事は
まずは足して10になる組み合わせを全て列挙してリスト化すると言うものですが、まず、それを列挙するアルゴリズムが思いつかないですし(フィボナッチ数的にできるかもとか考えましたけど全然違いました)
小数点以下切り捨ての問題もあるので単純な組み合わせではなく順列で列挙しないといけないのでは無いかと考えました。
今回はポイントが10なのでいいですが、100とかになると仮にそのアルゴリズムを思いついたとしても膨大な数になるのは目に見えています。
ポイントを使う回数も決められていないので、単純に足して10になるポイントの使い方を考えただけでも相当大きくなると思いますし列挙するのも簡単ではないと思います。

上記の問題は、Aの最大値を求めよと書いてあったので確かに答えは一意に求まる物のはずです。しかし組み合わせを全て列挙しないと最適解は求められないのでは?と言うのが私の疑問です。
どのように考えたらいいのでしょうか?よろしくお願いします。
ちなみにですけど、ソルバーなどのライブラリを使って解くという方法もあるかもしれないですが、きちんとアルゴリズムとしてその問題を解きたいです。
よろしくお願いします。

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • can110

    2018/11/08 06:13

    複利で効くので常にp=1×n回が最大をとると思いますが、そういうことではなく?組合せ列挙で求めたいということでしょうか?

    キャンセル

回答 6

+5

まず、Aの初期値が正値の場合、例示された漸化式なら常に1ポイントずつ利用していくのが解となります(切り捨て操作が入るけど結果に影響ないだろう)
すみません。初期値A=70などでは切り捨て影響して最適解ではなくなりますね。 2018/11/08 08:52修正
理由は説明できませんが、複利で効いてくるローンなどの利率計算と同じと考えてよいと思います。

しかしもし漸化式がもっと複雑だったり単調増加しないものであれば、ご推察のとおり全探索をする必要がでてきます。
その場合、ちょっと紙に書いて数え上げれば分かる通り、2^(N-1)通りの組み合わせが存在します。ここでN=ポイント数です。
この組み合わせの素朴な探索方法、すなわち解き方としては深さ優先探索というアルゴリズムが適しています。
これは「まずは足して10になる組み合わせを全て列挙」とは逆の発想で
「1~残ポイント数ずつひいていって0ポイントになるまで次の値を求めていく」という考え方をします。
たとえば以下のようなコードになります。
Online Python Tutorなどで実際に動かして動作を追ってみてください。

import math

# 次の値を返す
def next(A,p):
    return math.floor(A*(100+p)/100)

# (たぶん)厳密解
N = 10 # 利用可能な総ポイント数
A = 10000
for _ in range(N):
    A = next(A,1)
print('厳密解:',A) # 11045

# 探索
def search(A,remain,ret): # 現在値, 残ポイント, 結果(最大値)
    # 残ポイントなしなら最大値を記録
    if remain <= 0:
        if A > ret[0]:
            ret[0] = A
        return
    # 1...残ポイントずつ使って次の値を求める
    for p in range(1,remain+1):
        An = next(A,p)
        search(An,remain-p,ret) # 次の値を元に再帰で探索。残ポイントは現在の利用ポイント分を引く

A,ret = 10000,[-1] # 初期値と結果(最大値が格納される)
search(A,N,ret)
print('探索解:',ret[0]) # 11045


ただし実際に実行させてみると分かりますが、N=20を超えると実質時間がかかりすぎて解が求められなくなります。
速度アップするには順列生成をitertoolsに任せるなどの工夫が必要になってくるかと思います。

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/02/05 09:46

    返信くださりありがとうございます。
    その、呼出元に反映されない部分なのですがそれはint型がimmutableなオブジェクトでlist型がmutableなオブジェクトだからって認識で間違いないでしょうか?

    キャンセル

  • 2019/02/05 10:16

    どういう認識でimmutable/mutableというコトバを使っているかがちょっと理解できないので
    説明してただけると助かりますが…
    仮にint型の変数「a」がmutableだとした場合、a=123という代入結果が呼出元の変数「a」に反映されるという認識でmutableというコトバを使っているならば、合っているといっても良いかと思います。

    キャンセル

  • 2019/02/05 10:48

    大変失礼しました、、、
    immutable/mutable を持ってる値を変更できるできない程度の理解で使っていました。
    ご丁寧にありがとうございます

    キャンセル

+5

動的計画法に基づくアルゴリズムだと、初期ポイントをp_0として(p_0 + 1) * (p_0 / 2)回の計算で解を求めることができます。以下で、動的計画法に基づくアルゴリズムの考え方を説明します。

例えば、初期価値をA_0 = 100、初期ポイントをp_0 = 10の場合の問題を考えましょう。この問題をProblem(100, 10)と書くことにします。

最後に何ポイント使うかによって場合分けすると、以下の10通り考えることができます。

ケース1. 最後に1ポイントだけ使う場合、直前には9ポイント残っている
ケース2. 最後に2ポイント使う場合、直前には8ポイント残っている
...
ケース10. 最後に10ポイント全部使う場合、直前には0ポイント残っている

実はこれらの問題は、元の問題の部分問題の解を用いて上手く解くことができます。どういうことか見ていきましょう。

例えば、ケース2の場合の最適解は、直前の8ポイントの最適な使い方がわかっていれば実は簡単に求められます。つまり、初期価値をA_0 = 100、初期ポイントをp_0 = 8とした問題Problem(100, 8)の解がわかっていれば、ケース2の場合の最適解は、

ケース2の最適解 = Problem(100, 8)の最大価値 * (100 + 2) / 100(小数点以下切り捨て)

として求められます。

同様に、ケース1からケース10までの解はそれぞれ、

ケース1の最適解 = Problem(100, 9)の最大価値 * (100 + 1) / 100(小数点以下切り捨て)
ケース2の最適解 = Problem(100, 8)の最大価値 * (100 + 2) / 100(小数点以下切り捨て)
...
ケース10の最適解 = Problem(100, 0)の最大価値 * (100 + 10) / 100(小数点以下切り捨て)

となります。
ここで、ケース10の最適解で現れるProblem(100, 0)の最大価値は、明らかに100であることに注意してください。なぜなら、Problem(100, 0)は初期価値100で与えられたポイントが0だからです。

元の問題Problem(100, 10)の解は、ケース1からケース10の最適解のうち最も大きい価値を取るものになります。

このように、元の問題はより少ないポイントしか使えない状況下での最適解(部分問題の最適解)を用いて容易に計算できます。これを素朴に再帰を用いて実装したコードが一番下に書いてあるコードになります。

一方で、再帰を用いずにループだけで実装することも可能です。ループだけで実装する場合は、次のように考えるとよいです。

まず、Problem(100, 0)の解は上でも述べたように100であることは自明ですね。
次に、Problem(100, 1)の解はProblem(100, 0)の最大価値 * (100 + 1) / 100(小数点以下切り捨て)で計算できます。
次に、Problem(100, 2)の解は

最後に1ポイント使う場合: Problem(100, 1)の最大価値 * (100 + 1) / 100(小数点以下切り捨て)
最後に2ポイント使う場合: Problem(100, 0)の最大価値 * (100 + 2) / 100(小数点以下切り捨て)

のうち価値がより大きくなる方です。ただし、Problem(100, 1)の最大価値とProblem(100, 0)の最大価値はすでに求まっていることに注意してください。

次に、Problem(100, 3)の解は

最後に1ポイント使う場合: Problem(100, 2)の最大価値 * (100 + 1) / 100(小数点以下切り捨て)
最後に2ポイント使う場合: Problem(100, 1)の最大価値 * (100 + 2) / 100(小数点以下切り捨て)
最後に3ポイント使う場合: Problem(100, 0)の最大価値 * (100 + 3) / 100(小数点以下切り捨て)

のうち価値が最も大きくなるものです。ただし、Problem(100, 2)の最大価値とProblem(100, 1)の最大価値とProblem(100, 0)の最大価値はすでに求まっていることに注意してください。

このように与えられたポイントが小さい部分問題から順に解を求めていくことで単純なループで元の問題の解を求めることが可能です。
ループのみ再帰なしの実装を下に挙げます。

必要な計算回数はそれぞれ次のようになります。

Problem(100, 1): 1回
Problem(100, 2): 2回
Problem(100, 3): 3回
...
Problem(100, 10): 10回

なので、トータル(1 + 10) * (10 / 2) = 55回の計算で元の問題の解を求めることが可能です。

このように動的計画法では部分問題の解についての漸化式を用いて、より少ない計算量で元の問題の解を求めることができます。今回の問題においては、部分問題の解について以下の漸化式が成立していると解釈することができます。

Problem(A_0, p_0) = max_(p=1, ..., p_0) Problem(A_0, p_0 - p)の最大価値 * (100 + p) / 100(小数点以下切り捨て)

A_0 = 100
p_0 = 10


def solve(A_0, p_0):
    # Subproblem of this problem is defined by A_0 and p_0, each corresponds to
    # the initial value of some object and the points given initially.
    # Variable `solutions` holds the optimal values of subproblems as a dictionary.
    # The solution of the subproblem with (A_0, 0) is apparent, that is A_0.
    solutions = {(A_0, 0): A_0}
    for p_0 in range(1, p_0 + 1):
        # Solve the subproblem with (A_0, p_0), p_0 begins with 1
        # and ends with p_0 given to the function `solve`.
        max_A = A_0
        for point_to_be_used in range(1, p_0 + 1):
            # case division with the points to be used in the last time.
            A = solutions[(A_0, p_0 - point_to_be_used)] * (100 + point_to_be_used) // 100
            if A > max_A:
                max_A = A
        # add solution of the subproblem with (A_0, p_0)
        solutions.update({(A_0, p_0): max_A})
    return solutions[(A_0, p_0)]

print(solve(A_0, p_0))

以下、更新前の再帰に基づく実装です。

kichirb3さんの「小数点以下切り捨て」についての指摘を受けて改めて考え直した結果、解析的に閉じた形で解を求めることが難しいと思いました。

しかし、2^Nより効率の良いアルゴリズムを実装することは可能です。

動的計画法に基づいてより効率の良いアルゴリズムを実装しました。
今少し時間がないので取り急ぎ実装のみ上げておきます。
A_0やp_0を大きくして実行しても非常に高速に実行可能で、スケールします。
ただし、p_0をかなり大きくした場合には、Maximum Recursion Error(最大再帰呼び出し数の上限を超える)が発生しますが、pythonの再帰の上限を変更すればエラーは起こりません。
説明や計算量や補足については後ほど時間があるときに追記します。
計算量はちゃんと確認していませんが、多分O(p_0^2)です。計算時間がp_0^2にだいたい比例するということです。

from math import floor

original_A_0 = 100
original_p_0 = 10
solutions = {}

def formula(A, p):
    assert isinstance(A, int)
    assert isinstance(p, int)
    return A + floor(A * p / 100)


def solve(A_0, p_0):
    '''Return the maximum objective value of the problem with A_0 and p_0.'''
    assert isinstance(A_0, int)
    assert isinstance(p_0, int)
    if p_0 == 0:
        # if no points left, register solution and return back
        solutions.update({(A_0, p_0): A_0})
        return A_0
    if (A_0, p_0) in solutions:
        # if solution is already known, register solution and return back
        return solutions[(A_0, p_0)]

    maximum = A_0
    for p in range(1, p_0 + 1):
        A_previous = solve(A_0, p_0 - p)
        A_current = formula(A_previous, p)
        if A_current > maximum:
            maximum = A_current
    # register solution and return back
    solutions.update({(A_0, p_0): maximum})
    return maximum

maximum = solve(original_A_0, original_p_0)
print(maximum)

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/11/08 22:27

    すみません、他の方への回答を拝見したのですが、n=5までが一緒であればn=6以降はn=5までと一緒、と書いてありましたが、Aが10の時はポイントを10使う時のみ最適、のような例もあると思います。
    なので分割じゃなくて列挙しないといけないのでは?と思ってしまうのですが・・

    キャンセル

  • 2018/11/09 01:54

    他の方への回答の中で言及しているのは、特定の一例を用いてなぜ全探索に無駄が生じているのかを説明しているだけです。探索空間のどの部分が削減されているのか、について回答者様向けに説明したものです。
    そこで行なっている説明は動的計画法の自然な導出ではなく、どこが無駄になっていたか、という点について別の角度から説明したものです。
    この回答においてどのように考えれば自然に動的計画法が導出できるのか、については回答内にも記載の通り、まとまった時間が取れなかったので質問者様向けの動的計画法の考え方の説明が抜けております。少々お待ちくださいませ。

    キャンセル

  • 2018/11/15 09:44

    @babbleman 動的計画法に基づくアルゴリズムの説明を追記しました。また、再帰を使わずにループだけで実装したコードも追記しました。遅くなり申し訳ありません。

    キャンセル

+2

上記の問題は、Aの最大値を求めよと書いてあったので確かに答えは一意に求まる物のはずです。しかし組み合わせを全て列挙しないと最適解は求められないのでは?と言うのが私の疑問です。

can110さんのおっしゃる通り、任意の初期ポイントに対して最適解は常にポイントを1ポイントずつ使った場合になります。

ポイントを使う回数も決められていないので、単純に足して10になるポイントの使い方を考えただけでも相当大きくなると思いますし列挙するのも簡単ではないと思います。

おっしゃる通り、列挙アルゴリズムはややこしいです。ちなみにこの手の数え上げは場合の数のみを考える場合でさえ、効率の良い方法はないと思います。

以下に、最適解がなぜ1ポイントずつ使った場合になるのか説明します。


まず、初期ポイントが2ポイントである場合を考えましょう。ポイントの使い方は2通りあります。初期価値をv_0、最終価値をv_fとすると、それぞれ、

v_f_1 = v_0 * {(100 + 1) / 100} ^ 2 = v_0 * {1 + 1/100} ^ 2 = v_0 * {1 + 2/100 + ...}
v_f_2 = v_0 * {(100 + 2) / 100}     = v_0 * {1 + 2/100}

と書けます。どちらが大きいかを比べるためにv_f_1を展開しました。1ポイントずつ使った方が大きくなりますね。


次に、初期ポイントが3ポイントである場合を考えましょう。ポイントの使い方は2通りあります。1ポイントを3回に分けて使う場合と、1ポイントを1回と2ポイントを1回使う場合です。

v_f_1 = v_0 * {(100 + 1) / 100} ^ 3 = v_0 * {1 + 1/100} ^ 3 = v_0 * {1 + 3/100 + ...}
v_f_2 = v_0 * {(100 + 3) / 100}     = v_0 * {1 + 3/100}

と書けます。どちらが大きいかを比べるためにv_f_1を展開しました。1ポイントずつ使った方が大きくなりますね。


もうわかったかもしれませんが、一般にNポイントを1回で使うよりも1ポイントをN回使う方が大きくなります。これは二項定理よりすぐに成り立ちます。

さらに例えば、初期ポイントが10のとき、1ポイントを10回使った場合と(1, 2, 3, 4)の順で使った場合を比べると、

v_f_1 = v_0*{1 + 1/100} ^ 10
      = v_0*{1 + 1/100} + v_0*{1 + 1/100}^2+ v_0*{1 + 1/100}^3+ v_0*{1 + 1/100}^4
v_f_2 = v_0*{1 + 1/100} + v_0*{1 + 2/100}  + v_0*{1 + 3/100}  + v_0*{1 + 4/100}

となり、各項ごとに縦に比較すると、v_f_1の方が大きい方ことがわかります。
このように初期ポイントPを任意の分け方で分けた場合は、ポイントを1ポイントずつに分けた場合に比べて常に小さくなることがわかるはずです。
なので、任意のポイントの使い方のうち1ポイントずつ順に使う方法が価値を最大化するというわけです。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/11/08 08:40

    「小数点以下切り捨て」があるので、そう単純でもないように思います。たとえばA=10の場合、1ポイントずつ10回アップグレードしてもAの値は変化しないので、一度に10ポイント使う必要があります。また、A=70の場合、2+2+2+2+2でアップグレードするよりも3+3+4の方がAは大きくなります。

    キャンセル

  • 2018/11/08 08:45

    条件を見落としていました。たしかにおっしゃる通りです。ありがとうございます。もう一度考えてみます。

    キャンセル

  • 2018/11/08 08:56

    > A=70の場合、2+2+2+2+2でアップグレードするよりも3+3+4の方がAは大きくなります。
    たしかに。結果確認できましたので私の回答修正しました。
    ご指摘ありがとうございます。

    キャンセル

+2

ヒープキューに格納する際、残りポイント数を記録する必要はなさそうなので、Aの値(を-1倍したもの)のみを格納するようにしました。

from heapq import heappush, heappop

def solveA(A, point):
    status = [[-A] for _ in range(point + 1)]
    for i in range(point):
        A = heappop(status[i])
        for p in range(1, point - i + 1):
            heappush(status[i + p], (-(-A * (100 + p) // 100)))
    return -heappop(status[point])

以下は以前の解答です。

heapqを使って解いてみました。

from heapq import heappush, heappop

def solveA(A, point):
    status = [[] for _ in range(point + 1)]  # iポイント使った時の結果(Aと残りポイント)を格納するヒープキュー
    status[0].append((-A, point))  # 0ポイント消費時の(符号を逆にしたA, 残りポイント) を初期値として格納

    for i in range(point):
        A, remaining_point = heappop(status[i]) if status[i] else (0, 0, [])  # 同じiポイント使ったとき、Aの値が一番大きくなるケースをピックアップ
        A *= -1  # Aの符号を戻す
        for p in range(1, remaining_point + 1):
            heappush(status[i + p], (-(A * (100 + p) // 100), remaining_point-p))

    A, _  = heappop(status[point])
    return -A

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/11/08 16:31 編集

    これは前向きの、再帰を使わない動的計画法ですね。データ構造に優先度付きキューを利用している分、私の書いたアルゴリズムよりもmaxの評価にかかる計算量が削減されていますが、全体の計算量自体は私のものと同一ですね。heapqの仕様が最小値がルートに来るようになっているので、Aを全て負の値に直してからpushしているわけですね。
    今上がっている実装の中では最も効率の良いアルゴリズムだと思います。

    キャンセル

+1

追記2: Takahito_Ogawaさんにコメントいただき考えてみるとなるほど再帰的に最適解を求める考え方でよく、一度求めたa, pに関する最適解を複数回計算しなくてよいような論理が容易に組めることに気づけました。コメントありがとうございました。>Takahito_Ogawaさん

既にコードは複数上がっていて本質的には同じことだと思いますが、自分なりの「分かり易い」コードを書いてみました。例えばkichirb3さんのコードは再帰を必要としないコードですが、悲しいかなパっと見てすぐに腑に落ちなかった(^^;)ため自分なりに書いてみたわけです。

import math

debug_count = 0  # fを何回評価したかの計算量評価用カウンター

def f(a, p):
    global debug_count
    debug_count += 1
    return int(math.floor(a * (100 + p) / 100))

def solve(a, p):
    assert p > 0
    best = {}
    _count = debug_count

    def inner(p):
        # 既に(a, p)の最大値が計算済みなら単にそれを返す
        if p in best:
            return best[p]
        # 最初に全てのポイントを一度につぎ込んだ場合を計算
        max_a, max_ps = f(a, p), [p]
        for i in range(1, p):
            # p - iポイントをつぎ込んでからiポイントをつぎ込んだ場合を計算
            # まずp - iポイントをつぎ込んだ場合の最大値・組み合わせを再帰で求め>る
            pre_a, pre_ps = inner(p - i)
            # その後iポイントをつぎ込んだ最終結果を求める
            can_a = f(pre_a, i)
            # 最大値の更新
            if can_a > max_a:
                max_a, max_ps = can_a, pre_ps + [i]
        best[p] = max_a, max_ps
        return best[p]

    res = inner(p)
    return res + (debug_count - _count,)

print(solve(70, 10))     # (77, [10], 55)
print(solve(10000, 10))  # (11045, [1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 55)

追記:Takahito_Ogawaさんの動的計画法をちゃんと理解できてませんが、同じポイントを消費する組み合わせのうち最大のもの以外を候補から手際よく削除しながらベストなものの探索空間を絞り込むというアプローチではないかと思いました。それに対して本回答は劣っていて単にgen_psを示すためだけのものでしかないです。

なおポイント数11の最大値は10のときと同じなので1ポイントは無駄ということになり、無暗に組み合わせが増えているだけでありしらみつぶし探索のよくない特徴が浮き彫りになってますね。動的計画法であればこういう影響を受けず本質的に有効な組み合わせを早く求められるのではないかと思います。


足して10になる組み合わせを全て列挙してリスト化すると言うものですが、まず、それを列挙するアルゴリズムが思いつかない

実際には他の回答でのやりとりにあるように単に組み合わせではなく順列を加味した組み合わせになるのでしょうね・・・

1, 2
2, 1

を異なる組み合わせとみなすということです。リスト化する必要はないので一時に一つの組み合わせが列挙できれるようなiterator(実装ではgenerator)があればよいと思います。それは以下のgen_psのような感じで書けます。ポイントが10程度だとスタックオーバーフローの心配もないので最も単純と思える再帰を用いてます。

import math
import functools


def f(a, p):
    return math.floor(a * (100 + p) / 100)


def gen_ps(p, ps):
    for i in range(1, p):
        yield from gen_ps(p - i, ps + [i])
    yield ps + [p]


def solve(a0, p):
    print('initial A:', a0, 'total points:', p)
    count = 0
    max_a = a0
    best_pss = []
    for ps in gen_ps(p, []):
        count += 1
        a = functools.reduce(f, ps, a0)
        if a > max_a:
            # print(a, ps)
            max_a = a
            best_pss = [ps]
        elif a == max_a:
            best_pss.append(ps)
    print('maximum value: ', max_a)
    print('number of best combinations: ', len(best_pss))
    for ps in best_pss:
        print(ps)
    print('total number of checked candidates: ', count)


solve(70, 10)
solve(70, 11)

# 結果==>
initial A: 70 total points: 10
maximum value:  77
number of best combinations:  2
[3, 7]
[10]
total number of checked candidates:  512
initial A: 70 total points: 11
maximum value:  77
number of best combinations:  27
[1, 3, 7]
[1, 10]
[2, 2, 7]
[2, 3, 3, 3]
[2, 3, 6]
[2, 6, 3]
[2, 9]
[3, 1, 7]
[3, 2, 3, 3]
[3, 2, 6]
[3, 3, 2, 3]
[3, 3, 3, 2]
[3, 3, 5]
[3, 5, 3]
[3, 6, 2]
[3, 7, 1]
[3, 8]
[4, 7]
[5, 3, 3]
[5, 6]
[6, 2, 3]
[6, 3, 2]
[6, 5]
[8, 3]
[9, 2]
[10, 1]
[11]


上の解法は「どういう傾向の組み合わせが最大の価値につながるかが未知」という前提で「全ての組み合わせをしらみつぶしに試す」というアプローチです。

Aの初期値70についてやってみるとポイントが10の場合はベストな組み合わせは2通り、11になると27通りになりました。

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/11/09 02:03 編集

    その通りです。私の動的計画法の実装ではg(a, p)から始めて必要なg(a, 1)からg(a, p-1)をそれぞれ再帰的に計算していく方式で実装しています。ただし、一度計算した結果は保存して使い回しています。一方で、g(a, p)を計算するにはg(a, 1)からg(a, p-1)がわかればよいということは、再帰でなくてもg(a, 1)、g(a, 2)、g(a, 3)、...と前から順に計算していくこともできます。これを私は前向きの漸化式によって反復アルゴリズムで書ける、というように表現しております。

    キャンセル

  • 2018/11/09 02:21

    kichirb3さんの実装が前向きの反復アルゴリズムの実装になっています。その実装は読むのが少し難しいですが、基本的なアイデアは同じで、上手く書かれています。違うのは、データの保存方法だけです。私や貴方の実装ではg(a, 1)からg(a, p-1)のうちどれが一番価値を最大化できるかを求めるのに単純に反復して比較を行っていますが、kichirb3さんはここに優先度付きキューというデータ構造を用いることで最大値の計算を効率よく行おうとしてます。しかし、最大値の計算がいくら速くてもg(a, p)を求めるにはg(a, 1)からg(a, p-1)のそれぞれで計算を行う必要がありp-1回の計算を生むことには変わりがないので、計算コストは正直変わりません。

    キャンセル

  • 2018/11/09 11:59

    コメントありがとうございます。
    前向きアルゴリズムだと自分なら単にlistの要素にg(a, i)が格納されているとみなしてサブスクリプションによる記述にしそうです。pの組み合わせを求める処理を省略すると以下のようなイメージでしょうか。

    assert p > 0
    max_gs = [None] * (p + 1) # appendしてもいいけど最初から必要な大きさがわかっているので...
    for i in range(1, p + 1):
     max_gi = f(a, i)
     for j in range(1, i):
      max_gi = max(max_gi, f(max_gs[i - j], j))
     max_gs[i] = max_gi
    return max_gs[p]

    計算コストは同じでも人によって「自分にとってのわかりやすさ」「何を是とするか」が少しずつ違うような気がして面白いです。

    キャンセル

-1

すみません、2のn乗になる理由は簡単でしたね。
例えばp=3の時
◯◯◯の、間の2個をonにするか、offにするか、でしたね。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 88.58%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る