Python에서 막대를 절단하고 동일한 길이의 막대를 판매한 후 최대 이익을 찾는 프로그램

<시간/>

rodLen이라는 막대 길이 목록이 있다고 가정합니다. 길이당 이익과 절단당 비용을 나타내는 이익과 비용이라는 또 다른 두 개의 정수가 있습니다. 막대의 단위 길이당 이익을 얻을 수 있지만 길이가 모두 같은 막대만 판매할 수 있습니다. 막대의 길이가 정수가 되도록 두 조각으로 절단할 수도 있지만 절단할 때마다 비용을 지불해야 합니다. 우리는 원하는 만큼 막대를자를 수 있습니다. 우리는 우리가 만들 수 있는 최대의 이익을 찾아야 합니다.

따라서 입력이 rodLen =[7, 10] 이익 =6 비용 =4와 같으면 출력은 82가 됩니다. 길이 7의 막대를 길이가 5와 2인 두 막대로 자를 수 있기 때문입니다. 그런 다음 길이가 10인 막대를 길이가 5인 막대 두 개로 자릅니다. 그런 다음 길이가 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 / 컷
  - 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의 최대값
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