cut_rod.cpp File Reference

Implementation of cutting a rod problem. More...

#include <array>
#include <cassert>
#include <climits>
#include <cstdint>
#include <iostream>

Include dependency graph for cut_rod.cpp:

Go to the source code of this file.

Namespaces
namespace	dynamic_programming
	Dynamic Programming algorithms.
namespace	cut_rod
	Implementation of cutting a rod problem.

Functions
template<size_t T>
int	dynamic_programming::cut_rod::maxProfitByCuttingRod (const std::array< int, T > &price, const uint64_t &n)
	Cuts the rod in different pieces and stores the maximum profit for each piece of the rod.
static void	test ()
	Function to test above algorithm.
int	main ()
	Main function.

Detailed Description

Implementation of cutting a rod problem.

Given a rod of length n inches and an array of prices that contains prices of all pieces of size<=n. Determine the maximum profit obtainable by cutting up the rod and selling the pieces.

Algorithm

The idea is to break the given rod into every smaller piece as possible and then check profit for each piece, by calculating maximum profit for smaller pieces we will build the solution for larger pieces in bottom-up manner.

Author

Anmol

Pardeep

Definition in file cut_rod.cpp.

Function Documentation

main()

int main

(

void

)

Main function.

Returns

0 on exit

Definition at line 111 of file cut_rod.cpp.

           {
    // Testing
    test();
    return 0;
}

maxProfitByCuttingRod()

template<size_t T>

int dynamic_programming::cut_rod::maxProfitByCuttingRod	(	const std::array< int, T > &	price,
		const uint64_t &	n )

Cuts the rod in different pieces and stores the maximum profit for each piece of the rod.

Template Parameters

T	size of the price array

Parameters

n	size of the rod in inches
price	an array of prices that contains prices of all pieces of size<=n

Returns

maximum profit obtainable for

Parameters

n

inch rod.

Definition at line 45 of file cut_rod.cpp.

                                                                            {
    int *profit =
        new int[n + 1];  // profit[i] will hold maximum profit for i inch rod
 
    profit[0] = 0;  // if length of rod is zero, then no profit
 
    // outer loop will select size of rod, starting from 1 inch to n inch rod.
    // inner loop will evaluate the maximum profit we can get for i inch rod by
    // making every possible cut on it and will store it in profit[i].
    for (size_t i = 1; i <= n; i++) {
        int q = INT_MIN;
        for (size_t j = 1; j <= i; j++) {
            q = std::max(q, price[j - 1] + profit[i - j]);
        }
        profit[i] = q;
    }
    const int16_t ans = profit[n];
    delete[] profit;
    return ans;  // returning maximum profit
}

test()

static void test ( )

static

Function to test above algorithm.

Returns

void

Definition at line 72 of file cut_rod.cpp.

                   {
    // Test 1
    const int16_t n1 = 8;                                         // size of rod
    std::array<int32_t, n1> price1 = {1, 2, 4, 6, 8, 45, 21, 9};  // price array
    const int64_t max_profit1 =
        dynamic_programming::cut_rod::maxProfitByCuttingRod(price1, n1);
    const int64_t expected_max_profit1 = 47;
    assert(max_profit1 == expected_max_profit1);
    std::cout << "Maximum profit with " << n1 << " inch road is " << max_profit1
              << std::endl;
 
    // Test 2
    const int16_t n2 = 30;  // size of rod
    std::array<int32_t, n2> price2 = {
        1,  5,  8,  9,  10, 17, 17, 20, 24, 30,  // price array
        31, 32, 33, 34, 35, 36, 37, 38, 39, 40,
        41, 42, 43, 44, 45, 46, 47, 48, 49, 50};
 
    const int64_t max_profit2 =
        dynamic_programming::cut_rod::maxProfitByCuttingRod(price2, n2);
    const int32_t expected_max_profit2 = 90;
    assert(max_profit2 == expected_max_profit2);
    std::cout << "Maximum profit with " << n2 << " inch road is " << max_profit2
              << std::endl;
    // Test 3
    const int16_t n3 = 5;                                 // size of rod
    std::array<int32_t, n3> price3 = {2, 9, 17, 23, 45};  // price array
    const int64_t max_profit3 =
        dynamic_programming::cut_rod::maxProfitByCuttingRod(price3, n3);
    const int64_t expected_max_profit3 = 45;
    assert(max_profit3 == expected_max_profit3);
    std::cout << "Maximum profit with " << n3 << " inch road is " << max_profit3
              << std::endl;
}