2
\$\begingroup\$

I am learning dynamic programming. I read articles for the rod cutting problem and I applied it in cpp, and I got a doubt, does the below code solves the problem through memoization (say, previously rod(3) was solved, then if same function was called with same parameters) has the answer, or will it use tabulation (rodMax array), or uses both?

Since I read two different articles explaining different methods(memoization and tabulation, and read as two different methods to solve a dynamic problem), kind of confused on which method the below code runs.

#include <iostream>

using namespace std;

int max(int a, int b){

    if(a > b)
        return a;

    return b;
}

int arr[5] = {2, 4, 1, 2, 7};

int rodMax[5] = {-1, -1, -1, -1, -1};

int rod(int n){

    if(n <=0)
        return 0;

    if(rodMax[n - 1] != -1){
        return rodMax[n];
    }

    int max_val = -1;
    for(int i = 0; i < n; i++){

        max_val = max(max_val, arr[n-i-1]+rod(n-1));
    }
    //cout<<"\nmax "<<max_val<<endl;
    rodMax[n - 1] = max_val;

    return max_val;
}

int main() {

    cout<<"ans "<<rod(5)<<endl;
    //cout<<"ans "<<rod(3)<<endl;
    //for(int i = 0; i <5; i++)
    //  cout<<rodMax[i]<<" ";
}
```
\$\endgroup\$
  • 1
    \$\begingroup\$ Are you sure the code works? Did you test it with different use cases? \$\endgroup\$ – konijn Oct 30 '19 at 11:52
  • \$\begingroup\$ Hi Konijn, yes it works. Didn't test with many use cases. Just for implementation purpose, I read article and implemented it directly in C++. \$\endgroup\$ – susil95 Oct 30 '19 at 11:54
  • 1
    \$\begingroup\$ Could you please edit to summarise the "rod cutting problem", for those of us who don't recognise it from your description? Thanks. \$\endgroup\$ – Toby Speight Oct 30 '19 at 12:14
  • \$\begingroup\$ hey Toby, actually i got confused with tabulation and optimizing the code by using array to store intermediate results. \$\endgroup\$ – susil95 Oct 30 '19 at 12:36
  • \$\begingroup\$ en.wikipedia.org/wiki/Cutting_stock_problem \$\endgroup\$ – konijn Oct 30 '19 at 17:01
3
\$\begingroup\$
  • Use a consistent code style. Code style is a very important thing. It doesn't matter which one you choose, but any code style has to be consistent.
  • Choose appropriate names for entities. For example, it would be better to change the name of the rod function to something like cutRod, arr to prices, and so on.
  • Pass the list of prices directly to the function. It is better to avoid using global variables; pass the price array directly into the cutRod function:

    int cutRod(const int prices[], int length) {
        ...
    }
    
  • Don't use std::endl just as a new line symbol. std::endl is not the same as just \n. You should avoid using it globally.
  • Use appropriate type for counters that hold length of arrays. You should not use int as type for variables that hold length of arrays (such as i) because it is not guaranteed that int can hold maximal size of an array. Use std::size_t instead.
  • Why -1? I think it would be better to fill rodMax with INT_MIN instead of just -1.
  • Matter of taste, but... You can replace

    rodMax[n - 1] = max_val;
    return max_val;
    

    by a single line

    return (rodMax[n - 1] = max_val);
    
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Hi thanks for the review, most of them makes sense, and i'll use it. Especially for size_t, which i have used previously, and as i said it is just an quick implementation. I have a doubt @eanmos if we use return (rodMax[n - 1] = max_val);, doesn't it return true boolean value instead of the number which is max_val? \$\endgroup\$ – susil95 Oct 30 '19 at 15:32
  • \$\begingroup\$ @susil95, no, the = operator returns the new value of rodMax[n - 1] i. e. max_val. You'd be correct if we use == instead. \$\endgroup\$ – eanmos Oct 30 '19 at 16:07
  • \$\begingroup\$ Thanks for the info man. I just tried that, initially i used to think that anything with "=", will assign a value and gives an Boolean value, which is like acknowledging the statement that it ran, like if(cout<<"hello"), It prints hello and goes inside if block. \$\endgroup\$ – susil95 Oct 30 '19 at 17:36
  • \$\begingroup\$ @susil95, you're welcome) \$\endgroup\$ – eanmos Oct 30 '19 at 18:17
3
\$\begingroup\$

Don't using namespace std - especially if you're going to define a max() function in the global namespace (why not just use std::max() anyway? That's what it's for!).

Where do the values in arr and rodMax come from? Do their lengths have to agree? If so, make that obvious in the code (e.g. use std::array, so that we can use arr.size() to count the members).

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Hi values for arr(price of the rod) and rodMax(maximum price obtained after cutting the rod in different size). It should have been applied by std array. But just for quick implementation i wrote this. Thanks \$\endgroup\$ – susil95 Oct 30 '19 at 12:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.