c - 棒切割问题的递归自上而下实现中的价格不匹配

Question

我正在学习如何解决杆切割的最大利润问题。但是当我编写这段代码时，它并没有产生太大的结果。他给出的结果是 20，但正确的结果是 10。

这是代码:

#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;
}

这段代码有什么问题？

Answer 1

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

这是你的错误: cut_rod(prices, size - i - 1))和 for (int i = 0; i < size; i++)
这是一个算法规则。
请仔细阅读算法的描述。

你从 arr[1] = services[1] = 5(your values) 开始，但在描述算法中

我们应该从 arr[0] = price[0] = 1(your values) 开始

为了更好地理解你可以拿纸来解析这段代码(递归)

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