Rod резка - Динамическое программирование

Question

Постановка задачи

---

Проблема стержневой резки заключается в следующем. Учитывая стержень длины n дюймов и таблицу цен Pi для i = 1, 2, 3,....n, определите максимальный доход Rn, получая возможность разрезания стержня и продажи кусков. Обратите внимание, что если цена Pn для стержня длиной n достаточно велика, оптимальное решение может вообще не требовать резки.

Рассмотрите случай, когда n=4. На рисунке показаны все способы разрезания стержня длиной 4 дюйма, в том числе и без разрезов. Мы видим, что резка 4-дюймового стержня на две 2-дюймовые части дает доход P2+P2=5+5=10, что является оптимальным.

Ниже код является восходящим подходом строительного раствора для штоковой резки.

for (i = 1; i<=n; i++) 
{ 
    int q = INT_MIN; 
    for (j = 0; j < i; j++) 
     q= max(q, p[j] + r[i-j-1]); 
    r[i] = q; 
} 
return val[n]; 

Зачем нам нужен вспомогательный массив r[n+1]? Не удалось ли решить проблему, используя только массив p? Используется ли это потому, что мы не можем получить доступ к p [-1] при резке длины стержня n и 0? Почему мы используем q = max(q, p[j] + r[i-j-1]), когда p не обновлен до новых значений?

Answer 1

Если я правильно понял вопрос, то из реализации невозможно удалить r. По-видимому, семантика r является

r[i] = maximum profit attainabble by cutting a rod of length i 
     into pieces of the lengths 1,...,n 

, и она должна быть доступна во внутреннем цикле. Рекуррентное соотношение во внутреннем цикле переводит к

q = the more profitable choice between not cutting a rod of length j 
    and cutting a rod of length j (in which case we take p[j] as 
    profit plus the maximum attainable profit of cutting the remaining 
    rod, which has length j-i) 

, что означает, что информация в r необходима для оценки.

Answer 2

Проблема с резкой стержня без использования вспомогательного массива во внутреннем контуре и итерации его только наполовину.

#include <stdio.h> 
#include <limits.h> 

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

int cut_rod(int p[],int n) 
{ 
    int q=0; 
    int r[n+1]; // Auxiliary array for copying p and appending 0 at index 0 
    int i,j; 

    if(n<0) 
     return 0; 
    else 
    { 
     r[0]=0; 
     for(i=0;i<n;i++) 
      r[i+1]=p[i]; 
     for(i=1;i<=n+1;i++) 
     { 
      q=INT_MIN; 
      for(j=0;j<=i/2;j++) 
       q=max(q,r[j]+r[i-j-1]); 
      r[i-1]=q; 
     } 
    } 
    return r[n]; 
} 

int main() 
{ 
    int p[]={1,5,8,9,10,17,17,20,24,30}; 
    int n=sizeof(p)/sizeof(int); 
    int val; 

    val=cut_rod(p,n); 
    printf("%d",val); 

    return 0; 
} 

Answer 3

Вы должны использовать два различных массивов r и p, потому что их смысл совершенно другой. Значение p[i] сообщает вам, сколько стоит полная (не вырезанная) доска длиной i+1. Значение r[i] сообщает вам, сколько прибыли вы можете сделать с доской длины i+1 (полная или разрезанная на куски). Эти значения не совпадают. Например, в вашем примере у вас есть p[3] = 9, но r[3] = 10, потому что вы можете вырезать доску длиной 4 на две более мелкие части длиной 2. Сохранение двух разных значений в отдельных массивах - всегда хорошая идея. (За исключением случаев, когда у вас очень ограниченные ограничения памяти)

Кроме того, на практике вы, скорее всего, не будете продавать доски длиной 100. Но вам, возможно, захочется узнать оптимальную прибыль, которую вы можете сделать с доской такого размера путем резки Это. Если у вас есть только один массив, вам придется его увеличить. В зависимости от вашего выбора языка это также может потребовать создания второго массива и копирования первого массива. Поэтому было бы проще просто использовать второй массив.

Обратите внимание, что это возможно (если n меньше, чем длина массива p). Простым решением, которое использует только один массив, будет (с использованием одноиндексного):

int p[]={0,1,5,8,9,10,17,17,20,24,30}; 
int n = 4; 
for (int i = 1; i <= n; i++) 
{ 
    for (int j = 1; j <= i/2; j++) 
     p[i] = max(p[i], p[j] + p[i - j]); 
} 
printf("%d\n", p[n]);