Pythonでロッドを切断して同じ長さのロッドを販売した後に最大の利益を見つけるためのプログラム

rodLenと呼ばれるロッドの長さのリストがあるとします。また、利益とコストと呼ばれる別の2つの整数があり、長さあたりの利益とカットあたりのコストを表します。ロッドの単位長さあたりの利益は得られますが、販売できるのは同じ長さのロッドのみです。長さが整数になるようにロッドを2つに切断することもできますが、切断ごとに費用を支払う必要があります。ロッドは何度でもカットできます。自分たちが稼げる最大の利益を見つけなければなりません。

したがって、入力がrodLen =[7、10]利益=6コスト=4の場合、長さ7のロッドを長さ5と2の2つのロッドに切断できるため、出力は82になります。長さ10のロッドを両方とも長さ5の2つのロッドにカットします。次に、長さ5の3つのロッドすべてを販売して、合計利益（5 + 5 + 5）* 6-（2 * 4）=82にします。

これを解決するには、次の手順に従います-

• n：=rodLenのサイズ
• nが0と同じ場合、
  • 0を返す
• l_max：=rodLenの最大値
• p_max：=0
• 1からl_maxの範囲のカットについては、
  • p_cut：=0
  • rodLenのrod_lenごとに、
    を実行します。
    • rod_len <がカットされた場合、
      • 次の反復に進む
    • c_count：=rod_len / cuts
    • total_len：=c_count*カット
    • rod_lenがtotal_lenと同じ場合、
      • c_count：=c_count-1
    • curr_profit：=total_len*利益-コスト*c_count
    • curr_profit <0の場合、
      • 次の反復に進む
    • p_cut：=p_cut + curr_profit
  • p_max：=p_maxとp_cutの最大値
• return p_max

例

理解を深めるために、次の実装を見てみましょう-

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