【Python】ロッドを切断して同じ長さで販売したときの最大利益を求めるプログラム

ロッドの長さを格納したリスト rodLen があるとします。さらに、単位長さあたりの利益を表す整数 profit と、1回の切断にかかるコストを表す整数 cost が与えられます。ロッドからは長さに応じて利益を得られますが、販売できるのは「すべて同じ長さ」のロッドだけです。また、ロッドを長さが整数になるように2つの断片に切断することは可能ですが、切断1回ごとに cost の費用が発生します。切断の回数に制限はありません。ここで、得られる利益の最大値を求めます。

入力例と計算方法

たとえば、入力が rodLen = [7, 10]、profit = 6、cost = 4 である場合、出力は 82 になります。

具体的には、まず長さ7のロッドを長さ5と長さ2の2本に切断します。続いて、長さ10のロッドを長さ5の2本に切断します。こうして長さ5のロッドが3本そろうので、これらをすべて販売すると、合計利益は次のように計算できます。

(5 + 5 + 5) × 6 − (2 × 4) = 82

解法のアプローチ

この問題は、販売するロッドの長さとして考えられるすべての候補(1から最長のロッドの長さまで)を順に試し、それぞれの場合の利益を計算して最大値を取ることで解けます。手順は以下のとおりです。

• n := rodLen の要素数とする
• n が 0 の場合は 0 を返す
• l_max := rodLen の最大値
• p_max := 0(答えとなる最大利益)
• cuts を 1 から l_max まで変化させながら以下を繰り返す
  • p_cut := 0(この長さで販売した場合の利益)
  • rodLen の各 rod_len について以下を処理する
    • rod_len が cuts 未満であれば、次のロッドへスキップする
    • c_count := rod_len ÷ cuts(切り出せるピースの数)
    • total_len := c_count × cuts(実際に販売できる合計の長さ)
    • rod_len と total_len が等しい(割り切れる)場合は、c_count := c_count − 1 とする
    • curr_profit := total_len × profit − cost × c_count(このロッドから得られる利益)
    • curr_profit が負になる場合はスキップする
    • p_cut := p_cut + curr_profit
  • p_max := p_max と p_cut の大きい方
• 最後に p_max を返す

ここでのポイントは、1本のロッドを k 個のピースに分割するとき、必要な切断回数は k − 1 回であるという点です。そのため、ロッドが指定の長さで割り切れる場合には c_count を 1 減らしています。

Pythonでの実装例

理解を深めるために、以下の実装を見てみましょう。

def solve(rodLen, profit, cost):
    n = len(rodLen)
    if n == 0:
        return 0
    l_max = max(rodLen)
    p_max = 0

    for cuts in range(1, l_max + 1):
        p_cut = 0
        for rod_len in rodLen:
            if rod_len < cuts:
                continue
            c_count = rod_len // cuts
            total_len = c_count * cuts
            if rod_len == total_len:
                c_count -= 1
            curr_profit = total_len * profit - cost * c_count
            if curr_profit < 0:
                continue
            p_cut += curr_profit
        p_max = max(p_max, p_cut)
    return p_max

rodLen = [7, 10]
profit = 6
cost = 4
print(solve(rodLen, profit, cost))

入力

[7, 10], 6, 4

出力

82

計算量について

この手法では、販売長の候補ごとにすべてのロッドを走査するため、時間計算量は O(l_max × n) となります。ロッドの本数と最大長がそこまで大きくなければ十分実用的なアプローチです。