so then I was watching the lecture and I thought at the time it would be nice to try implement the example (well, partially at least) used in the lecture.
I have two questions:
- Is my approach to this problem from the recursion perspestive correct? I am struggling with the recursion a lot, trying to understand it in depth.
- Could you guys recommend me some good material/books/etc about the recursion and how can I understand it better?
The rod problem:
Suppose you have a rod of length n, and you want to cut up the rod and sell the pieces in a way that maximizes the total amount of money you get.
My code (in c++):
#include "stdafx.h"
#include <iostream>
#include <string>
#include <map>
using namespace std;
// Main struct
struct rd_value {
int profit = 0; // Profit that we will gain from the particular rod size.
string rod_ap = ""; // How it would look like ( for style purposes only ).
};
// Just a data structure to tie a struct with a particular rod size.
map<int,rd_value> rod_values;
// It holds our current rod data,
// we will populate it in the function cut_rod.
rd_value current;
// Global ints to ease the work/
int n, orig;
int cut_rod(int pos)
{
// Add the style strings and the profit into our current struct.
current.profit += rod_values[pos].profit;
current.rod_ap += rod_values[pos].rod_ap + " ";
// Subtract the cut position from the length of the rod
// aka we are selling the cut side immediatly as said in the video.
n -= pos;
// 1) If our rod can support the same cut after the initial cut,
// do it again
// 2) If it can't do 1), try to cut it by one less.
// 3) If it can't do 1) and 2), just cut it by the it's current length
// ( actually we are not cutting it now, but for the simplicity purposes
// let say we are.
// 4) Exit if we are out of cutting options.
// 4) is first because it would trigger stack overflow eventually
// if it were in the end it will trigger stack overflow.
if (n <= 0) // 4)
return 0;
else if (n >= pos) // 1)
cut_rod(pos);
else if (n >= pos - 1) // 2)
cut_rod(pos - 1);
else if (n != 0) // 3)
cut_rod(n);
}
void init_def_values()
{
// A void function to initialize the selling points for the rods.
// Could be replaced with a text file approach or something to hold all/some
// precomputed rod values to speed the solving process.
rod_values[1].profit = 1;
rod_values[1].rod_ap = "*";
rod_values[2].profit = 5;
rod_values[2].rod_ap = "**";
rod_values[3].profit = 8;
rod_values[3].rod_ap = "***";
rod_values[4].profit = 10;
rod_values[4].rod_ap = "** **";
}
int main()
{
init_def_values();
// Entering the length of our rod.
cout << "Please Enter your rod length:";
cin >> orig;
n = orig;
// Exit the program if the length is not valid.
if (n <= 0)
return 0;
// Serve the purpose of a look-up table, if we had all/some of the values in a text file for e.g.
if (rod_values[n].profit != 0)
cout << "You would get: " << rod_values[n].profit << " and the cut rods look like: " << rod_values[n].rod_ap << endl;
else
{
// Why we are starting at 3rd position?
// Because it makes more sense after all:
// 1) most economically viable lengths are 2 and 3, they
// bring the most profit to us, so we start at 3 and move down if neeeded
// 2) length of 4 is useless except of the length value itself, because it does make
// more sense to just cut it the 4 length into two smaller peaces of length 2,
// thus making 10 profit instead of 8.
cut_rod(3);
cout << "Current rod profit: " << current.profit << " and it looks like: " << current.rod_ap << endl;
}
system("Pause");
return 0;
}