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

Question

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

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

Comments

[can110]

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

Answer 1

動的計画法に基づくアルゴリズムだと、初期ポイントを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)

Comments

[babbleman]

回答をどうもありがとうございます。
assertなど見慣れない言語がありましたので、書いていただいたプログラムを手で書きながら意味を調べてみます。

[Takahito_Ogawa]

assert isinstance(A, int)は変数Aがintでなければエラーを出すという意味です。デバッグのためにいれています。ちょっと時間がないのでコードも難しめになっています。

[Takahito_Ogawa]

再帰を用いて後ろ向きの漸化式で実装しましたが、普通のループで前向きの漸化式で実装することもできるので後で実装と解説を上げておきます。

[babbleman]

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

[Takahito_Ogawa]

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

[Takahito_Ogawa]

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

Answer 2

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

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

Comments

[Takahito_Ogawa]

組み合わせの数2^N通りではありません。例えばN=2の場合は、2^2=4になりますが、実際には(1, 1), (2)の2通りです。N=3の場合は、2^3=8になりますが、実際には(1, 1, 1), (1, 2), (3)の3通りです（(2, 1)は(1, 2)と等価なので注意）。私の回答に記載している通り、一般にこの手の場合の数は何通りあるかを考えるだけでも難しいです（もちろんプログラムで数え上げれば可能ではあります）。

[can110]

ご指摘ありがとうございます。
(2, 1)と(1, 2)を別とみた場合、2^(N-1)ですね。
ちなみになのですが(2, 1)と(1, 2)で結果が異なるような漸化式も考えられないでしょうか？
その場合は2^(N-1)通りの探索必要と思いますが、いかがでしょうか？
いまちょっと良い例式が思いつきませんが。

[Takahito_Ogawa]

組み合わせの数は2^(N-1)でもないと思います。どうやら重複を(1, 2), (2, 1)許容して数えているようですが、その場合でも2^(N-1)ではないように思います。例えば、N=4の場合は、2^3=8になりますが、重複を許しても(1, 1, 1, 1), (1, 1, 2), (1, 2, 1), (2, 1, 1), (1, 3), (3, 1), (4)の7通りしかありません。

[can110]

> (1, 1, 1, 1), (1, 1, 2), (1, 2, 1), (2, 1, 1), (1, 3), (3, 1), (4)の7通り
(2,2)が抜けてないでしょうか？

[Takahito_Ogawa]

>ちなみになのですが(2, 1)と(1, 2)で結果が異なるような漸化式も考えられないでしょうか？
一般には考えられます。そもそも今の例で(2, 1)と(1, 2)の結果が一緒になるのは、漸化式が行っていることが、「今回与えられたpのみに基づいて(100+p)/100倍する」という操作になっているからです。
結果が異なるような漸化式にするためには、やり方はいくつかありますが、一番シンプルなものを高校数学の言葉でいうと三項間漸化式を用いることです。例えば、A(後)＝A(前)×A(前の前)×(100＋p)/100とかにすると、結果は変わるはずです。他には、A(後)＝A(前)^2×(100＋p)/100のようにしても結果が変わるはずです。三項間漸化式は1個前の値にも依存するようにすることによって、後者はもう少しA(前)の依存性をあげた形になります。

[Takahito_Ogawa]

あっ確かにぬけてますね。

[can110]

なるほど。やはり一般的には考えられますね。
詳細なコメントありがとうございます。勉強になります。
しかし数え上げをちゃんとやるのはおっしゃる通りややこしいです(^-^;

[Takahito_Ogawa]

重複を許した場合に2^(N-1)になることがちゃんと一般のNの場合で確かめられました。

[Takahito_Ogawa]

ちなみにここでは深さ優先探索の方が直感的に理解しやすいから(?)それで実装されていますが、幅優先探索でもかかる時間は同じです。

[can110]

理解プラス実装しやすさで深さ優先を採用しました。
かかる時間は根本的にはどちらも同じですね。

[babbleman]

わかりやすい回答をどうもありがとうございます。
すみません、なぜ2^(n-1)乗になるのでしょう？確かに数えたらそうなりましたが、数学的にも知っておきたいです。
それと、再帰プログラムがわからないです。最初のループで1が代入され、次のループでremainが9、p=2が代入されて条件に従ってreturnで抜ければ、結果は「1、2、3、4」の1通りになるのではないでしょうか？

[can110]

再帰についてだけ。理解するには実際に動かして動作の流れを追うしかないです。確認に便利なサイトについて追記しました。

[babbleman]

すみません、漸化式の立て方も教えていただけないでしょうか？
Pを変数とするのはわかるのですが、具体的な立て方がわからないです・・・

[babbleman]

ありがとうございます、サイトを確認してみます。

[can110]

すみません。何が分からないのかが分かりません。
「漸化式の立て方」とは具体的にどういったことでしょう？
質問文に示された漸化式
「A(後)＝A(前)×(100＋p)/100(小数点以下切り捨て)」
をコードに置き換えただけなのですが…

[babbleman]

すみません、再帰プログラムについてはアッカーマン関数を書いた事があるのでわかるのですが、やはりfor文の処理というものがわかりません。簡単に教えていただけます？

[babbleman]

もう一つお願いします。皆さんn=70の時の解を出していますが、n=40の時点で100万の二乗です、どのようにして確かめたんですか？

[Takahito_Ogawa]

皆さんが出しているのはn=70の場合ではなく、A=70の場合です。あなたがおっしゃるように私以外の回答にあるアルゴリズムは2^(n-1)回計算が必要になるので、n=40の時点で100万の二乗になるのでもはや計算できません。私のアルゴリズムではn^2回プラスアルファしか計算が必要ないので、n=20のような巨大なnの場合でも一瞬で計算が終わります。

[kuraudo]

@can110 さん
こちらのコードを読み、自分の手元でも確認して一点だけ不明だったのが結果を出力するために使っている変数retを配列型(リスト)ではなくint型を使えないのはなんでなんでしょうか？
宜しければ教えて頂けると幸いです。

[can110]

引数retをint型にすると、ret = 123と代入した結果は呼出元に反映されないため、リスト型にしています。
つまりC++言語での func( int &ret)と同じことをPythonでもやりたかったので、そうしています。

return retのように戻り値で結果を返すのが素直な書き方かと思います。

[kuraudo]

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

[can110]

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

[kuraudo]

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

Answer 3

ヒープキューに格納する際、残りポイント数を記録する必要はなさそうなので、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

Comments

[Takahito_Ogawa]

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

Answer 4

上記の問題は、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ポイントずつ順に使う方法が価値を最大化するというわけです。

Comments

[退会済みユーザー]

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

[Takahito_Ogawa]

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

[can110]

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

Answer 5

追記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通りになりました。

Comments

[Takahito_Ogawa]

追記を拝見しました。探索の基本は計算の無駄の排除ですから、その観点からなぜしらみつぶしが無駄かをコメントしておきます。
例えば10ポイント与えられたとして、最初のちょうど5ポイントを使うまでの最適なポイントの使い方(配分方法1)が分かっていたとします。このとき、他のちょうど5ポイントを使うまでの任意のポイントの使い方はそれ以降の6ポイント目からの使い方を考える必要がなくなります。なぜなら、例え6ポイント目以降でどれだけ上手くポイントを使ったとしても、配分方法1で6ポイント目以降の使い方を同じにしたものよりも必ず最終価値が小さくなってしまうからです。
つまり、6ポイント目以降の配分方法を考えることは無駄になります。
この考え方をつき詰めていくと、結局各ポイントまでの最適配分方法が分かればいいということになり動的計画法に辿り着きます。

[KSwordOfHaste]

コメントありがとうございました。この問題をg(a, p)として、

最初「単にg(a, p-1)が求まっているだけではg(a, p)は求まらないよな・・・」と思ってしまったのですが、何のことはない「g(a, 1)～g(a, p-1)まで全て求まっていればそこからg(a, p)はp-1回だけの試行で求まるではないか」ということに気づけました。

[Takahito_Ogawa]

その通りです。私の動的計画法の実装では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)、...と前から順に計算していくこともできます。これを私は前向きの漸化式によって反復アルゴリズムで書ける、というように表現しております。

[Takahito_Ogawa]

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

[KSwordOfHaste]

コメントありがとうございます。
前向きアルゴリズムだと自分なら単に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]

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

Answer 6

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