C++에서 길이가 다른 막대를 절단하여 최대 이익을 찾는 프로그램

<시간/>

길이가 n인 막대가 있다고 가정합니다. 또한 각 크기에 대해 다른 크기와 가격이 포함된 목록이 있습니다. 막대를 잘라서 시장에 팔아서 최고가를 찾아야 한다. 낚싯대를 절단한 후 다른 위치에서 절단하고 가격을 비교하여 최상의 가격을 얻으십시오.

따라서 입력이 가격 =[1, 5, 8, 9, 10, 17, 17, 20], n =8인 경우 출력은 막대를 길이 2와 6으로 자르는 것과 같이 22가 됩니다. 이익은 5 + 17 =22입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

n+1 크기의 어레이 이익을 정의합니다.
이익[0] :=0
initialize i :=1의 경우, i <=n일 때 업데이트(i를 1만큼 증가), −
- maxProfit :=음의 무한대
- j 초기화의 경우:=0, j
  - maxProfit :=maxProfit 및 price[j] + 이익[i − j − 1]
    의 최대값
- 이익[i] :=maxProfit
maxProfit을 반환

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#include <bits/stdc++.h>
using namespace std;
int max(int a, int b) {
   return (a > b)? a : b;
}
int rodCutting(int price[], int n) {
   int profit[n+1];
   profit[0] = 0;
   int maxProfit;
   for (int i = 1; i<=n; i++) {
      maxProfit = INT_MIN;
      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 << rodCutting(priceList, rodLength);
}

입력

{1, 5, 8, 9, 10, 17, 17, 20}, 8