dynamic-programming
막대 절단

최대 이익을 얻으려면로드를 자르십시오.

길이 n 인치의 막대와 n 보다 작은 모든 크기의 가격을 포함하는 가격 m 의 배열을 감안할 때. 막대를 자르고 조각을 팔아 얻을 수있는 최대 가치를 찾아야합니다. 예를 들어 막대의 길이가 8 이고 다른 조각의 값이 다음과 같이 주어진 경우 최대 얻을 수있는 값은 22 입니다.

       +---+---+---+---+---+---+---+---+
 (price)| 1 | 5 | 8 | 9 | 10| 17| 17| 20|
        +---+---+---+---+---+---+---+---+

우리는 2 차원 배열 dp [m] [n + 1]을 사용합니다. 여기서 n은 막대의 길이이고 m은 가격 배열의 길이입니다. 예제에서는 dp [8] [9]가 필요 합니다. 여기에서 dp [i] [j] 는 길이 j의 막대를 판매하여 최대 가격을 나타냅니다. 길이 j의 최대 값을 전체적으로 가질 수도 있고 이익을 최대화하기 위해 길이를 줄일 수도 있습니다.

처음에 0 번째 열에 대해서는 아무것도 기여하지 않으므로 모든 값을 0으로 표시합니다. 그래서 0 번째 열의 모든 값은 0이됩니다. dp [0] [1]의 경우 우리가 얻을 수있는 최대 값은 얼마입니까? 우리는 길이 2 dp [0] [2]의 막대에 대해서도 마찬가지입니다. 우리는 2 (1 + 1)을 가질 수 있습니다. 이것은 dp [0] [8] 까지 계속됩니다. 첫 번째 반복 이후 우리의 dp [] 배열은 다음과 같이 보일 것입니다.

      +---+---+---+---+---+---+---+---+---+
 (price)| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
        +---+---+---+---+---+---+---+---+---+
  (1) 1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 9 |
        +---+---+---+---+---+---+---+---+---+
  (5) 2 | 0 |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+---+
  (8) 3 | 0 |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+---+
  (9) 4 | 0 |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+---+
 (10) 5 | 0 |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+---+
 (17) 6 | 0 |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+---+
 (17) 7 | 0 |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+---+
 (20) 8 | 0 |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+---+

dp [2] [2] 우리는 두 개의 막대 (1, 1) 또는 막대를 전체 (길이 = 2)로 떼어 내면 내가 얻을 수있는 최선의 것이 무엇인지 물어볼 것입니다. 우리는 만약 내가 막대를 두 조각으로 쪼개면 최대 이익은 2이고 만약 막대가 전체적으로 나올 수 있다면 그것을 팔 수 있습니다 5. 두 번째 반복 후에 dp [] 배열은 다음과 같이 보일 것입니다 :

     +---+---+---+---+---+---+---+---+---+
 (price)| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
        +---+---+---+---+---+---+---+---+---+
  (1) 1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 9 |
        +---+---+---+---+---+---+---+---+---+
  (5) 2 | 0 | 1 | 5 | 6 | 10| 11| 15| 16| 20|
        +---+---+---+---+---+---+---+---+---+
  (8) 3 | 0 |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+---+
  (9) 4 | 0 |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+---+
 (10) 5 | 0 |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+---+
 (17) 6 | 0 |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+---+
 (17) 7 | 0 |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+---+
 (20) 8 | 0 |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+---+ 

따라서 dp [i] [j]를 계산하려면 공식이 다음과 같을 것입니다 :

if j>=i
    dp[i][j] = Max(dp[i-1][j], price[i]+arr[i][j-i]);
else
    dp[i][j] = dp[i-1][j];

마지막 반복 후에 우리의 dp [] 배열은 다음과 같이 보입니다.

       +---+---+---+---+---+---+---+---+---+
 (price)| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
        +---+---+---+---+---+---+---+---+---+
  (1) 1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 9 |
        +---+---+---+---+---+---+---+---+---+
  (5) 2 | 0 | 1 | 5 | 6 | 10| 11| 15| 16| 20|
        +---+---+---+---+---+---+---+---+---+
  (8) 3 | 0 | 1 | 5 | 8 | 10| 13| 16| 18| 21|
        +---+---+---+---+---+---+---+---+---+
  (9) 4 | 0 | 1 | 5 | 8 | 10| 13| 16| 18| 21|
        +---+---+---+---+---+---+---+---+---+
 (10) 5 | 0 | 1 | 5 | 8 | 10| 13| 16| 18| 21|
        +---+---+---+---+---+---+---+---+---+
 (17) 6 | 0 | 1 | 5 | 8 | 10| 13| 17| 18| 22|
        +---+---+---+---+---+---+---+---+---+
 (17) 7 | 0 | 1 | 5 | 8 | 10| 13| 17| 18| 22|
        +---+---+---+---+---+---+---+---+---+
 (20) 8 | 0 | 1 | 5 | 8 | 10| 13| 17| 18| 22|
        +---+---+---+---+---+---+---+---+---+

우리는 dp [n] [m + 1] 에서 그 결과를 얻을 것입니다.

Java로 구현

public int getMaximumPrice(int price[],int n){
        int arr[][] = new int[n][price.length+1];
        
        for(int i=0;i<n;i++){
            for(int j=0;j<price.length+1;j++){
                if(j==0 || i==0)
                    arr[i][j] = 0;
                else if(j>=i){
                    arr[i][j] = Math.max(arr[i-1][j], price[i-1]+arr[i][j-i]);
                }else{
                    arr[i][j] = arr[i-1][j];
                }
            }
        }
        return arr[n-1][price.length];
    }

시간 복잡성

O(n^2)