고유 길이 값으로 자른 막대의 최대 총 가격을 계산하십시오.

Question

막대 절단 문제 (길이가 n 인 막대가 n> 0, n은 정수이고, 정수 길이의 조각으로 자르고 싶음) 총 가격이 최대화 되었음), p는 가격 목록, n은 막대의 길이입니다. 나는 최대 값을 얻기 위해 막대를 자르고 싶습니다. 그 동안 우리는 또한 길이가 unqiue인지 확인해야합니다. 즉, 이미 조각 길이 = 3, 다른 조각 길이 = 3을 절단 할 수없는 경우입니다.

예를 들어 벡터 p = {1,5,8,9,10,12,17,20}; 최대 가격 : 21, 길이 : 2,3,3. 그래서 결과는 20이되어야하고 길이는 2,3,3 대신에 830이됩니다.

어떻게하면 코드를 수정하고 시간 복잡성을 유지할 수 있습니까? O (n^2) 감사.

int n = 8; 
vector<int> p = {1,5,8,9,10,12,17,20}; 

void cut_rod(vector<int>& p, int n){ 

    int r[n+1]; 
    int s[n+1]; 
    r[0] = 0; 

    for (int j = 1; j<=n; j++){ 
     int q = INT_MIN; 
     for (int i = 1; i <= j; i++){ 
      if(q < p[i-1] + r[j-i]){ 

       q = p[i-1] + r[j-i]; 
       s[j] = i; 
      } 
     } 
     r[j] = q; 
    } 
    return r[n]; 

} 

Answer 1

주어진 길이만큼 조각을 저장할 때 n + 1 행렬을 사용할 수 있습니다. 이렇게하면 일정한 시간 내에 동일한 크기의 조각이 있는지 확인하고 행을 복사하면 선형 시간이 걸리므로 복잡성은 여전히 ​​O (n^2)이지만 공간 복잡성은 O (n^2)입니다.

아래의 geeksforgeeks 코드를 수정했습니다.

// A Dynamic Programming solution for Rod cutting problem 
#include<stdio.h> 
#include<limits.h> 
using namespace std; 
// A utility function to get the maximum of two integers 
int max(int a, int b) { return (a > b)? a : b;} 

/* Returns the best obtainable price for a rod of length n and 
price[] as prices of different pieces */ 
int cutRod(int price[], int n) 
{ 
    int pieces[n+1][n+1];  
    int val[n+1]; 
    val[0] = 0; 
    int i, j; 

    // Build the table val[] in bottom up manner and return the last entry 
    // from the table 
    for (i = 1; i<=n; i++) 
    { 
     int max_val = INT_MIN, ind = -1; 
     for (j = 1; j <= i; j++) { 
      if (max_val < price[j - 1] + val[i-j]) { 
       if (pieces[i-j][j] != 1) {     
        max_val = price[j - 1] + val[i-j]; 
        ind = j; 
       } 
      } 
     } 
     val[i] = max_val; 
     for (int k = 0; k <= n; ++k) { // Copy the pieces 
      pieces[i][k] = pieces[i-ind][k]; 
     } 
     pieces[i][ind] = 1; // Add the piece of length ind (which is the max j) 
    } 
    return val[n]; 
} 

/* Driver program to test above functions */ 
int main() 
{ 
    int arr[] = {1,5,8,9,10,12,17,20}; 
    int size = sizeof(arr)/sizeof(arr[0]); 
    printf("Maximum Obtainable Value is %dn", cutRod(arr, size)); 
    getchar(); 
    return 0; 
} 

민주당 알고리즘 어레이 발의 i 번째 위치에 저장 그 길이 I로로드에 대해, N 0에서 최대 가격 간다. 우리는 길이가 i 인 막대의 컷을 0에서 n까지가는 배열 인 조각들 [i]에 저장합니다. 만약 위치 j에서 1이라면 최대 값 val [i]를 얻는 것을 의미합니다. 조각이 있어야합니다 길이 j의 이제, 어떤 길이 i에 대한 DP 알고리즘은 길이 j의 컷을 만들고 길이 j의 가격의 가격과 이미 계산 된 길이 i-j의 나머지 부분의 최대 가격의 합을 계산합니다. 이 합계는 일부 j에 대한 최대 값을 가지며, 이는 가격 [j - 1] + val [i - j]가 최대 일 것임을 의미합니다 (여기서 j는 이미 존재하지 않습니다). 이제 길이 i에 대해 길이 j의 조각과 길이 i - j의 조각을 조각 [i - j]에 저장했습니다. 이제 조각을 얻으려면 [i - j] 조각을 복사하고 길이 j 조각을 추가해야합니다. 당신이 1 문자 변수 이름을 사용하는 이유는

당신은 그

for (int i = 0; i <= n; ++i) 
    if (pieces[n][i] == 1) cout << i << ' ';