Java中切杆问题的3种解决方案

切杆问题（棒切割：Rod Cutting Problem）是一个经典的优化问题，涉及找到将棒切割成碎片的最佳方法，以最大化总收入。

什么是切杆问题
假设我们有一根长度为 n 的杆，我们可以灵活地将这根杆切割成各种长度，然后出售这些切割段。此外，我们还拥有一份不同长度切割棒的价格表。我们的目标是使总收入最大化。

例如，考虑长度为 n=4 的棒材，价格 Pi = [1,5,8,9]。Pi 数组表示长度为 i 的棒材的价格：

P1 = 1 表示长度为 1 的棒的价格为 1 个单位。

P2 = 5 表示长度为 2 的杆件的价格为 5 个单位。

同样，P3 = 8 表示长度为 3 的杆件的价格为 8 个单位，而 P2 = 5 表示长度为 2 的杆件的价格为 5 个单位。

P4 = 9 表示长度为 4 的杆件的价格为 9 个单位。

我们可以对棒材进行各种切割，每次切割都会根据棒材的价格带来一定的收入。以下是长度为 4 的棒的可能切割：

• 切成 4 段，每段长度 1 米[1,1,1,1]，收入 = 1+1+1+1 = 4 美元
• 切成 2 段，每段长度 2 米[2,2]，收入 = 5+5 = 10 美元
• 切割成长度为 4 米的 1 块，收入 = 9 美元
• 切割成 3 块长度分别为 1 米和 2 米的木板 [1,1,2]，收入 = 1+1+5 = 7 美元
• 切割成 3 块长度分别为 1 米和 2 米的木板 [1,2,1]，收入 = 1+5+1 = 7 美元
• 切成长度分别为 1 米和 2 米的 3 块 [2,1,1]，收入= 5+1+1 = 7 美元

1、简单递归解法
递归解决方案涉及将问题分解为子问题并递归地解决它们。

int usingRecursion(int[] prices, int n) {
    if (n <= 0) {
        return 0;
    }
    int maxRevenue = Integer.MIN_VALUE;
    for (int i = 1; i <= n; i++) {
        maxRevenue = Math.max(maxRevenue, prices[i - 1] + usingRecursion(prices, n - i));
    }
    return maxRevenue;
}

在我们的示例中，我们检查基本情况以确定杆的长度是否等于或小于 0，从而导致收入为 0。我们使用递归系统地探索所有潜在的切割，以计算每次切割的最大收入。结果是所有削减中实现的最高收入。

现在，让我们测试一下这种方法：

@Test
void givenARod_whenUsingRecursion_thenFindMaxRevenue() {
    int[] prices = {1, 5, 8, 9};
    int rodLength = 4;
    int maxRevenue = RodCuttingProblem.usingRecursion(prices, rodLength);
    assertEquals(10, maxRevenue);
}

递归方法有效并且相对容易理解。然而，其指数时间复杂度 O(2 n ) 使其对于较大的实例来说不切实际，因为递归调用将迅速增加。

因此，如果我们有一根 4m 的杆，这种方法将需要 2的 4次幂 = 16 次迭代。

这种方法缺乏记忆会导致冗余计算，因为在递归探索过程中会多次解决相同的子问题。对于具有相当长度的杆的实际场景来说，这种低效率成为一个重要问题。

2、记忆递归解决方案
我们可以通过使用记忆来改进我们的递归解决方案。在这种方法中，我们将使用记忆表来存储和重用先前解决的子问题的结果：

int usingMemoizedRecursion(int[] prices, int n) {
    int[] memo = new int[n + 1];
    Arrays.fill(memo, -1);
    return memoizedHelper(prices, n, memo);
}
int memoizedHelper(int[] prices, int n, int[] memo) {
    if (n <= 0) {
        return 0;
    }
    if (memo[n] != -1) {
        return memo[n];
    }
    int maxRevenue = Integer.MIN_VALUE;
    for (int i = 1; i <= n; i++) {
        maxRevenue = Math.max(maxRevenue, prices[i - 1] + memoizedHelper(prices, n - i, memo));
    }
    memo[n] = maxRevenue;
    return maxRevenue;
}

这个想法是通过在再次解决子问题之前检查子问题是否已经解决来避免冗余计算。我们的记忆表采用数组的形式，其中每个索引对应于杆的长度，并且关联的值保存该特定长度的最大收入。

现在，让我们测试一下这种方法：

@Test
void givenARod_whenUsingMemoizedRecursion_thenFindMaxRevenue() {
    int[] prices = {1, 5, 8, 9};
    int rodLength = 4;
    int maxRevenue = RodCuttingProblem.usingMemoizedRecursion(prices, rodLength);
    assertEquals(10, maxRevenue);
}

这意味着对于长度为 10m 的杆，我们的时间复杂度为 100，而之前为 1024，因为由于节点的修剪，我们所做的工作显着减少。然而，这是以空间复杂度为代价的。之前的算法不存储任何状态，而这个算法需要为每个可能的杆长度存储最多一个值，从而使其空间复杂度为 O(n)。

3、动态规划解决方案
解决这个问题的另一种方法是通过动态规划。动态规划通过将问题分解为更小的子问题来解决问题。这与分治算法求解技术非常相似。然而，主要的区别在于动态规划只能解决子问题一次。

 迭代（自下而上）方法
在这种方法中，避免递归并使用迭代过程消除了与递归解决方案相关的函数调用开销，从而有助于增强性能：

int usingDynamicProgramming(int[] prices, int n) {
    int[] dp = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        int maxRevenue = Integer.MIN_VALUE;
        for (int j = 1; j <= i; j++) {
            maxRevenue = Math.max(maxRevenue, prices[j - 1] + dp[i - j]);
        }
        dp = maxRevenue;
    }
    return dp[n];
}

测试：

 int[] prices = {1, 5, 8, 9};
    int rodLength = 4;
    int maxRevenue = RodCuttingProblem.usingDynamicProgramming(prices, rodLength);
    assertEquals(10, maxRevenue);

我们的动态规划表由dp数组表示，存储每个子问题的最优解，其中索引i对应杆长度，dp保存最大收益。dp数组中的最后一项dp[n]包含长度为 n 的杆的原始问题的最大收益。

这种方法也节省内存，因为它不需要额外的记忆表。

无界背包解决方案
无界背包方法是一种动态规划技术，用于解决可以无限次选择某个项目的优化问题。这意味着，如果有助于最大化收入，则可以多次选择相同的切割长度并将其包含在杆中。

我们看一下实现：

int usingUnboundedKnapsack(int[] prices, int n) {
    int[] dp = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < prices.length; j++) {
            if (j + 1 <= i) {
                dp[i] = Math.max(dp[i], dp[i - (j + 1)] + prices[j]);
            }
        }
    }
    return dp[n];
}

 int[] prices = {1, 5, 8, 9};
    int rodLength = 4;
    int maxRevenue = RodCuttingProblem.usingUnboundedKnapsack(prices, rodLength);
    assertEquals(10, maxRevenue);