Sunjaree

Rod Cutting DP

Dec 4th, 2021
760
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using  namespace  std;
  3. #define endl         "\n"
  4. #define ll           long long
  5.  
  6.  
  7. int cutRod(int price[], int n)
  8. {
  9.     int val[n+1];
  10.     val[0] = 0;
  11.  
  12.     for (int i = 1; i<=n; i++){
  13.  
  14.         int max_val = INT_MIN;
  15.         for (int j = 0; j < i; j++) {
  16.            
  17.             int v = val[i - j - 1];
  18.             max_val = max(max_val, price[j] + v);
  19.         }
  20.         val[i] = max_val;
  21.     }
  22.  
  23.     return val[n];
  24. }
  25.  
  26. int main()
  27. {
  28.     int arr[] = {1, 5, 8, 9, 10, 17, 17, 20};
  29.  
  30.     // here length of the rod is n
  31.     int n = sizeof(arr) / sizeof(arr[0]);
  32.     cout <<"Maximum Obtainable Value is "<<cutRod(arr, n);
  33.     return 0;
  34. }
  35.  
  36.  
RAW Paste Data