로드 커팅

길이가 n인 막대가 있습니다. 각 크기에 대해 다른 크기와 가격을 포함하는 다른 테이블도 제공됩니다. 봉을 절단하여 시장에 판매하여 최고가를 결정합니다.

낚싯대를 절단한 후 위치를 다르게 하여 가격을 비교하여 최적의 가격을 얻기 위함입니다.

f(n)이 길이가 n인 행을 자른 후 가능한 최대 가격을 반환하도록 하십시오. 다음과 같이 f(n) 함수를 간단히 작성할 수 있습니다.

f(n) :=price[i]+f(n – i – 1)의 최대 값, 여기서 i는 0에서 (n – 1) 범위에 있습니다.

입력 및 출력

입력 :

다른 길이의 가격과 막대의 길이. 여기서 길이는 8입니다.

출력 :

판매 후 최대 수익은 22입니다.

막대를 길이 2와 6으로 자릅니다. 이익은 5 + 17 =22입니다.

알고리즘

rodCutting(price, n)

입력: 가격 목록, 목록에 있는 여러 가격

출력: 절단 막대를 통한 최대 수익.

Begin
   define profit array of size n + 1
   profit[0] := 0
   for i := 1 to n, do
      maxProfit := - ∞
      for j := 0 to i-1, do
         maxProfit := maximum of maxProfit and (price[j] + profit[i-j-1])
      done

      profit[i] := maxProfit
   done
   return maxProfit
End

예시

#include <iostream>
using namespace std;

int max(int a, int b) {
   return (a > b)? a : b;
}

int rodCutting(int price[], int n) {    //from price and length of n, find max profit
   int profit[n+1];
   profit[0] = 0;
   int maxProfit;

   for (int i = 1; i<=n; i++) {
      maxProfit = INT_MIN;    //initially set as -ve infinity
      for (int j = 0; j < i; j++)
         maxProfit = max(maxProfit, price[j] + profit[i-j-1]);
      profit[i] = maxProfit;
   }
   return maxProfit;
}

int main() {
   int priceList[] = {1, 5, 8, 9, 10, 17, 17, 20};
   int rodLength = 8;
   cout << "Maximum Price: "<< rodCutting(priceList, rodLength);
}

출력

Maximum Price: 22