Price mismatch in recursive top-down implementation of rod cutting problem

user_11080661 0
Viewed 2211

I'm learning how to solve problem about maximum profit of rod cutting. But when I wrote this code, it produced not a drastic result. It he gives the result 20, but the correct result is 10.

Here is code:

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

int _max(int a, int b) { if (a > b) return a; else return b; }

int cut_rod(int prices[], int size)
{
    if (size == 0) return size;

    int max = 0;
    for (int i = 1; i <= size; i++)
    {
        max = _max(max, prices[i] + cut_rod(prices, size - i));
    }

    return max;
}

int main(int argc, char** argv)
{
    int arr[] = { 1,5,8,9};
    int size = sizeof(arr) / sizeof(arr[0]);

    int max = cut_rod(arr, size);
    printf("Maximum Obtainable Value is %d", max);
    getchar();
    return 0;
}

What can be wrong in this code?

dynamic-programming c
2 Answers
for (int i = 0; i < size; i++)
{
    max = _max(max, prices[i] + cut_rod(prices, size - i - 1));
}

This is your mistake: cut_rod(prices, size - i - 1)) and for (int i = 0; i < size; i++)

This is an algorithm rule. Please read the description of the algorithms carefully.

You start with arr[1] = prices[1] = 5(your values) but in description algorithm

We should start with arr[0] = prices[0] = 1(your values)

For better understanding you can take paper and parse this piece of code (recursion)

for (int i = 0; i < size; i++)
{
    max = _max(max, prices[i] + cut_rod(prices, size - i - 1));
}
user_134169120

You access the arr[]/prices[] array out of bounds in

for (int i = 1; i <= size; i++)
{
    max = _max(max, prices[i] + cut_rod(prices, size - i));
}

since array indexes start counting at 0 in C. Size is 4 but there is no arr[4].

user_6486580
Related