-2

Given a rod of length n inches and an array of prices that contains prices of all pieces of size smaller than n. Determine the locations where the cuts are to be made for maximum profit.

I need help how can we approach this problem ?

user10891599
  • 41
  • 1
  • 5

1 Answers1

0

A simple recursion can solve this problem:

#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;
}

On the other hand, this solution is slow. The best option would be taking the knapsack problem approach: consider you have a knapsack of size n and each piece of size (or weight in this case) i costs p[i], then just fill the matrix as the common knapsack would do. The idea would be to preprocess the best price for itens at each size until n.

eesiraed
  • 4,626
  • 4
  • 16
  • 34
Daniel
  • 7,357
  • 7
  • 32
  • 84
  • The first two lines are probably some of the worst things that you can write in an interview. See https://stackoverflow.com/q/31816095/9254539. – eesiraed May 04 '20 at 21:30
  • The question is about an algorithm, not about includes and namespaces. Do you have any consideration about the algorithm or my comments? I don't think you are judging the main point of the answer. – Daniel May 04 '20 at 21:59
  • It's not the main point of your answer, but many people who sees this won't know any better and will think `#include ` is the right way to go. There are already enough bad C++ teachers out there teaching bad practices. Is writing two proper standard library `#include` lines really that hard? – eesiraed May 04 '20 at 22:24
  • No, but a general include line is easier if the point of the explanation is not about the includes but the logics of an algorithm. I'm pretty sure someone who asked about an algorithm won't mind which includes I used. Anyway, feel free to edit my answer. – Daniel May 04 '20 at 22:28