Проблема резания стержня - PullRequest
Новая
       4

Проблема резания стержня

0 голосов
/ 23 марта 2020

Если вы знакомы с алгоритмом резки стержня, вопрос находится внизу.

В следующем алгоритме (код C ++) rev - это массив, содержащий максимальный доход, который может иметь стержень заданной длины. , в то время как ценовой массив для стандартной цены без разрезания стержня на дальнейшие части. Приведенный ниже алгоритм - это то, что я нахожу из многих источников, чтобы найти максимальный доход стержня длины n. 

    int cutRod(int price[], int n) 
    { 
       int rev[n+1]; 
       rev[0] = 0; 
       int i, j; 
       for (i = 1; i<=n; i++) 
       { 
           int max_val = INT_MIN; 
           for (j = 0; j < i; j++) 
              max_val = max(max_val, price[j] + rev[i-j-1]); 
           val[i] = max_val; 
       } 
       return val[n]; 
    }

Как видно, этот алгоритм работает, разрезая стержень на две части, при этом одна часть не разрезается дальше (мы учитываем ее цену), а другая часть может быть разрезана (мы рассматриваем ее доход) , Это означает, что мы должны были бы сделать это n раз, учитывая, что нужно отрезать разные длины.

ВОПРОС: Почему мы не можем заставить этот l oop выполнить половину числа итераций, передавая только доход от обеих частей? а не одна цена и один доход, потому что доход содержит информацию о том, является ли цена максимальной, если прут обрезан или не обрезан? Разве это не будет более эффективным? Проще говоря: price[1]<=rev[1], price[2]<=rev[2], ... Таким образом, для стержня длиной n = 3 вместо того, чтобы найти максимум из: price[1]+rev[2], price[2]+rev[1], price[3]+rev[0] (n elements) , мы могли бы просто найти максимум: rev[1]+rev[2],rev[3]+rev[0] (⌊n/2⌋ + 1 elements)

1 Ответ

1 голос
/ 23 марта 2020

Да, вы можете реализовать это, скопировав цены в массив выручки (занимает O(n)), а затем только взглянув на выручку разбиений на размер i+j, где i<j. И должен получить коэффициент увеличения скорости в 2 раза.

Но это также усложняет логику c, что мешает использовать это в качестве простой демонстрационной задачи для динамического программирования c. Суть не в том, чтобы найти фактор улучшения 2 алгоритмов c, а в том, чтобы улучшить биг- O.

Во-вторых, проблема имеет много вариантов. В той, на которую вы смотрели, есть цена для каждой длины стержня. Но что, если у вас есть цены на некоторые длины, но не на другие? (Например, США продают гвозди с длинами, указанными с шагом 1/4 дюйма, но, как показывает https://www.homedepot.com/c/ab/types-of-nails/9ba683603be9fa5395fab909c451e98, мы продаем только некоторые длины гвоздей.) Более простая задача обобщает лучше.

...