막대 자르기를 위한 Python 프로그램

이 기사에서는 아래 주어진 문제 설명에 대한 솔루션에 대해 알아볼 것입니다.

문제 설명 − 길이가 n인 막대와 n보다 작은 크기의 모든 조각의 가격을 포함하는 가격 배열이 주어집니다. 막대를 자르고 조각을 팔아서 얻을 수 있는 최대 가치를 결정해야 합니다.

우리는 문제를 해결하기 위해 동적 프로그래밍 접근 방식을 사용할 것입니다.

이제 아래 구현에서 솔루션을 살펴보겠습니다-

예시

# A Dynamic Programming solution for Rod cutting problem
INT_MIN = -32767
# cut function
def cutRod(price, n):
   val = [0 for x in range(n + 1)]
   val[0] = 0
   # bottom up manner
   for i in range(1, n + 1):
      max_val = INT_MIN
      for j in range(i):
         max_val = max(max_val, price[j] + val[i-j-1])
      val[i] = max_val
   return val[n]
# main
arr = [2, 4, 7, 9, 11, 16, 16, 21]
size = len(arr)
print("Maximum Obtainable Value is " + str(cutRod(arr, size)))

출력

Maximum Obtainable Value is 21

모든 변수는 로컬 범위에서 선언되며 해당 참조는 위 그림과 같습니다.

결론

이 기사에서 우리는 막대를 자르기 위한 Python 프로그램을 만드는 방법에 대해 배웠습니다.