найти места в проблеме резки прута [интервью Microsoft]

Question

Учитывая стержень длиной n дюймов и массив цен, который содержит цены на все кусочки размером меньше n. Определите места, где должны быть сделаны сокращения для максимальной прибыли.

Мне нужна помощь, как мы можем решить эту проблему?

Answer 1

Простая рекурсия может решить эту проблему:

#include <algorithm>
#include <climits>

int maxPrice(int prices[], int n) { 
   if (n <= 0) return 0; 
   int ans = INT_MIN; 

   for (int i = 0; i < n; i++) 
         ans = std::max(ans, prices[i] + maxPrice(prices, n - i - 1)); 

   return ans; 
} 

int main(){
    //size:         1  2  3  4  5   6   7   8
    int prices[] = {1, 3, 4, 8, 9, 11, 11, 16};
    std::cout<<maxPrice(prices, 8)<<std::endl;
    return 0;
}

С другой стороны, это решение медленное. Лучшим вариантом будет подход к решению проблемы с рюкзаком: учтите, что у вас есть рюкзак размером n и каждый кусок размера (или веса в данном случае) i стоит p [ я] , затем просто заполните матрицу, как сделал бы обычный рюкзак. Идея состояла бы в том, чтобы предварительно обработать лучшую цену для итенов для каждого размера до n .