C++ Cutting Rod Dynamic programming

Question

I am new to dynamic programming and trying to solve an evergreen problem: cutting rod. I have been trying for hours and I am stuck. I am trying to debug it but without success. Here is my code

#include <iostream>
#include <cstdlib>
using namespace std;

int main()
{
    int length = 5;
    int peaces[2][4] = {{1, 2, 3, 4}, {2, 5, 7, 8}};
    /*
        length  1, 2, 3, 4
        value:  2, 5, 7, 8  
    */ 

    //create working matrix: number of lengths X lengths
    int work[4][6];
    //fill in the first column with zeros
    for(  int k = 0; k < 5; k++  )
    {
        work[k][0] = 0;
    }
    //fill in the first row with zeroes
    for(  int k = 0; k <= length; k++  )
    {
        work[0][k] = 0;
    }

    for(  int i = 1; i < 5; i++  ) // number of lengths
    {
        cout << endl << " i: " << i << "   " << endl;
        for(  int j = 1; j < 6; j++  )
        {
            cout << endl << " j: " << j << "   " << endl;
            if(  j >= i  )
            {
                work[i][j] = max(  work[i - 1][j], work[i][j - i] + peaces[1][i-1]  );
            }
            else
            {
                work[i][j] = work[i - 1][j];
            }
            cout << endl;<< "inserted:" << work[i][j]<< endl;

            for(  int i = 0; i < 5; i++  )
            {
                for(  int j = 0; j < 6; j++  )
                {
                    cout << work[i][j] << " ";          
                }
                cout << endl;
            }

            cout  <<  endl;
        }
    }



    for(  int i = 0; i < 5; i++  )
    {
        for(  int j = 0; j < 6; j++  )
        {
            cout << work[i][j] << " ";          
        }
        cout << endl;
    }

    return 0;   
};

Something very strange happens and I can't figure out why: in the last iteration of the for loop I get right solution, but when exit the loop and I print the 2D array, it is changed, not the same as the one in the last iteration. Between two printing no operation is done on the array. I know that this is not an optimized solution, but that is the first one I have come up with. Question: Why is not the array filled the right way? What have I done wrong?

The main issue that I see is that you array length of the first dimension is incorrect. You have work[4][6] and twice you are referencing it "for( int k = 0; k < 5; k++ )" and later "for( int i = 0; i < 5; i++ )", when you should be only going up to an index of 3. In C++, all arrays are referenced as zero-based collections. So, you can reference the array using 0,1,2,3. Therefore, you should be using k < 4 and i < 4. This will help you narrow down your issues. — wandercoder, Nov 21 '15 at 16:22
Thank you a looot! The first array I worked with had 4 rows, later on I added one to because I needed it for iteration, and forgot to increase number of rows when I defined it. So thank you again. I have spent so much time debugging but without success. I wanted to be sure that I tried everything before I post question. — Nemanja Neca, Nov 21 '15 at 16:43
This is an example of where using `std::array` is useful because you always have the length information available to you without needing to keep track of yet another variable. Also the printing out of the array would be best in it's own function to reduce code duplication. — shuttle87, Nov 21 '15 at 17:31
Thanks for the tips. I didn't know about std::array. I will start using it. — Nemanja Neca, Nov 25 '15 at 00:41

score 0 · Accepted Answer · edited May 23 '17 at 12:15

0

The best way to avoid issues like this is to define variables for the dimensions in the first place. For example,

int xlen = 4;
int ylen = 5;
int work[xlen][ylen];

Then, you can use xlen and ylen in your loops and if you want to change the size of the arrays, you just change the xlen and ylen.

Alternatively, you can find the size using answers that you find here: How do I find the length of an array?

And finally, you should read up on the standard template library, which gives you "smarter" objects you can use.

edited May 23 '17 at 12:15

Community

1
1

answered Nov 21 '15 at 17:35

wandercoder

392
2
16

I definitely need to start learning STL's. I was focused on learning data structures, sorting algorithms and dynamic programming. Now I see that it is useful to learn more about them – Nemanja Neca Nov 25 '15 at 00:44

C++ Cutting Rod Dynamic programming

1 Answers1