Çubuk kesme algoritmasında tüm çubuk kesme uzunluklarını nasıl bilebilirim? (dinamik programlama)

Question

Çubuk kesme algoritmasını biliyorum. C++ uygulaması aşağıdaki gibidir:

Maximum Obtainable Value is 22 

Sorum i belli uzunluktaki çubuk kesme maksimum değerini (fiyat) bulabilirsiniz ama nasıl ben uzunluğunu bulabilirsiniz:

// A Dynamic Programming solution for Rod cutting problem 
#include<stdio.h> 
#include<limits.h> 

// 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 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; 
     for (j = 0; j < i; j++) 
     max_val = max(max_val, price[j] + val[i-j-1]); 
     val[i] = max_val; 
    } 

    return val[n]; 
} 

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

çıkışı Bu özel çubukta keser?

Answer 1

CutRod işlevini güncelleyebilirsiniz, böylece aşağıdan yukarıya doğru yaklaşırken, adresinden de'u kullanmayı deneyin. (yani bu aşamaya ulaşmak için kestiğiniz son çubuk) Bir kez bittikten sonra, geri dönmeden önce, geldiğiniz son noktadan başlayabilir ve 0'a gelene kadar keseceğiniz her çubuğu takip edebilirsiniz. Aşağıdan yukarıya yaklaşımınız için temel.

Aşağıda ham bir uygulama bulabilirsiniz.

int numRodsUsed; 
int cutRod(int price[], int rods[], int n) 
{ 
    int val[n+1]; 
    int lastRod[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; 
     int best_rod_len = -1; 
     for (j = 0; j < i; j++) 
     { 
      if(max_val < price[j] + val[i-j-1]) 
      { 
       max_val = price[j] + val[i-j-1]; 
       best_rod_len = j; 
      } 
     } 
     val[i] = max_val; 
     lastRod[i] = best_rod_len + 1; 
    } 

    for (i = n, j = 0; i>0; i -= lastRod[i]) 
    { 
     rods[j++] = lastRod[i]; 
    } 
    numRodsUsed = j; 

    return val[n]; 
} 

int main() 
{ 
    int arr[] = {1, 5, 8, 9, 10, 17, 17, 20}; 
    int size = sizeof(arr)/sizeof(arr[0]); 
    int rods[size+1]; 
    int i; 
    printf("Maximum Obtainable Value is %d\n", cutRod(arr, rods, size)); 
    printf("Rod lengths are: %d", rods[0]); 
    for(i = 1; i < numRodsUsed; i++) 
    { 
     printf(" %d", rods[i]); 
    } 
    printf("\n"); 
    getchar(); 
    return 0; 
}