Solving Rod Cutting Problem in Java – 用 Java 解决切杆问题

最后修改: 2024年 2月 24日

中文/混合/英文(键盘快捷键：t)

1. Overview

1.概述

The Rod Cutting Problem is a classic optimization problem that involves finding the best way to cut a rod into pieces to maximize the total revenue.

棒材切割问题是一个经典的优化问题，涉及寻找将棒材切割成碎片的最佳方法，以实现总收入最大化。

In this tutorial, we’ll understand the Rod Cutting Problem and explore various approaches to solving it in Java.

在本教程中，我们将了解 Rod Cutting Problem 并探索用 Java 解决该问题的各种方法。

2. Understanding the Problem

2.了解问题

Imagine we’ve got a rod of length n. We’ve got the flexibility to cut this rod into various lengths and sell those cut segments. Furthermore, we possess a table of prices for different lengths of cut rods. Our goal is to maximize the total revenue.

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

For example, consider a rod of length n=4 with prices Pi = [1,5,8,9]. The Pi array denotes the price of a rod piece of length i. It means:

例如，考虑长度为 n=4 的杆，价格 Pi = [1,5,8,9]。Pi 数组表示长度为 i 的杆件的价格。意思是

P1 = 1 shows the price of a rod piece of length 1 is 1 unit.

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

P2 = 5 shows the price of a rod piece of length 2 is 5 units.

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

Similarly, P3 = 8 shows the price of a rod piece of length 3 is 8 units, and

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

P4 = 9 shows the price of a rod piece of length 4 is 9 units.

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

We can make various cuts to the rod, and each cut will result in a certain revenue based on the prices of the rod pieces. Here are the possible cuts for a rod of length 4:

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

  • Cut into 4 pieces of length 1m each [1,1,1,1], resulted in revenue = 1+1+1+1 = $4
  • Cut into 2 pieces of length 2m each [2,2], resulted in revenue = 5+5 = $10
  • Cut into 1 piece of length 4m, resulted in revenue = $9
  • Cut into 3 pieces of length 1m and 2m [1,1,2], resulted in revenue = 1+1+5 = $7
  • Cut into 3 pieces of length 1m and 2m [1,2,1], resulted in revenue = 1+5+1 = $7
  • Cut into 3 pieces of length 1m and 2m [2,1,1], resulted in revenue= 5+1+1 = $7

Here, we can see that by cutting our rod into 2 pieces of length 2m each, we get a total price of $10. Every other combination gives a lower price, so we can see that this is the optimal answer.

在这里，我们可以看到，把我们的竿子切成两段，每段长 2 米，我们得到的总价是 10 美元。其他每种组合的价格都更低，因此我们可以看出这是最佳答案。

3. Recursive Solution

3.递归解决方案

The recursive solution involves decomposing the problem into subproblems and solving them recursively. The recurrence relation used to calculate the maximum revenue for a rod of length n is Rn = max1<=i<=n(Pi+Rn-i).

递归解涉及将问题分解为子问题并递归求解。 计算长度为n的杆的最大收益所使用的递推关系为 Rn = max1<=i<=n(Pi+Rn-i).

In the above relation, Rn represents the maximum revenue for a rod of length n, and Pi is the price of a rod piece of length i. Let’s implement the recursive solution:

在上述关系式中，Rn表示长度为n的钓竿的最大收益，Pi表示长度为i的钓竿的价格。让我们来实现递归解：

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

In our example, we check the base case to determine if the rod’s length is equal to or less than 0, resulting in a revenue of 0. We systematically explore all potential cuts using recursion to calculate the maximum revenue for each cut. The result is the highest revenue achieved among all the cuts.

在我们的示例中，我们检查基本情况，以确定杆的长度是否等于或小于 0，从而得到 0 收入。结果就是在所有切割中取得的最高收益。

Now, let’s test this approach:

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

<span class="pl-c1">@</span><span class="pl-c1"><span class="pl-token">Test</span></span><br />void givenARod_whenUsingRecursion_thenFindMaxRevenue() {
    int[] prices = {1, 5, 8, 9};
    int rodLength = 4;
    int maxRevenue = RodCuttingProblem.usingRecursion(prices, rodLength);
    assertEquals(10, maxRevenue);
}

The recursive approach works and is relatively easy to understand. However, its exponential time complexity O(2n) makes it impractical for larger instances, as recursive calls will rapidly increase. So, if we’ve got a 4m rod, this approach will take 24 = 16 iterations.

递归方法行之有效，而且相对容易理解。然而，其指数时间复杂度为 O(2n)，对于较大的实例来说并不实用，因为递归调用会迅速增加。因此，如果我们有一根 4 米长的鱼竿，这种方法将需要 24 = 16 次迭代。

The lack of memorization in this approach results in redundant computations, as identical subproblems are solved multiple times during the recursive exploration. This inefficiency becomes a significant concern for realistic scenarios with rods of considerable lengths.

这种方法缺乏记忆，导致计算冗余，因为在递归探索过程中，相同的子问题会被多次求解。这种低效率的问题在实际场景中会非常突出，因为杆的长度相当长。

4. Memoized Recursive Solution

4.记忆递归解决方案

We can improve our recursive solution by the use of memoization. In this approach, we’ll use a memoization table to store and reuse the results of previously solved subproblems:

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

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

The idea is to avoid redundant computations by checking whether a subproblem has already been solved before solving it again. Our memoization table takes the form of an array, where each index corresponds to the rod length, and the associated value holds the maximum revenue for that specific length.

这样做的目的是在再次求解子问题之前，检查该子问题是否已经解决，从而避免重复计算。我们的备忘表采用数组形式，其中每个索引都与杆的长度相对应，相关的值为该特定长度的最大收益。

Now, let’s test this approach:

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

<span class="pl-c1">@</span><span class="pl-c1"><span class="pl-token">Test</span></span><br />void givenARod_whenUsingMemoizedRecursion_thenFindMaxRevenue() {
    int[] prices = {1, 5, 8, 9};
    int rodLength = 4;
    int maxRevenue = RodCuttingProblem.usingMemoizedRecursion(prices, rodLength);
    assertEquals(10, maxRevenue);
}

By avoiding the redundant calculations through memoization, the time complexity is significantly reduced compared to the naive recursive solution. Now, the time complexity is determined by the number of unique subproblems solved, and for the Rod Cutting problem, it is often O(n2) due to the two nested loops.

通过 memoization 避免了冗余计算，时间复杂度比天真的递归解法大大降低。现在，时间复杂度由求解的唯一子问题的数量决定，对于杆切割问题，由于存在两个嵌套循环，时间复杂度通常为 O(n2)。

This means for a rod of length 10m, we’ll have a time complexity of 100 here, compared to 1024 before, because we’re doing notably less work due to the trimming of nodes. However, this comes at a cost in space complexity. The previous algorithm didn’t store any state, whereas this one will need to store up to one value for each possible rod length, giving it a space complexity of O(n).

这意味着，对于长度为 10 米的杆件，我们的时间复杂度为 100，而之前为 1024，因为由于对节点进行了修剪，我们所做的工作明显减少了。然而，这需要付出空间复杂度的代价。之前的算法不存储任何状态，而现在的算法则需要为每个可能的杆长度存储一个值，因此空间复杂度为 O(n)。

5. Dynamic Programming Solution

5.动态编程解决方案

Another approach to solving this problem is via dynamic programming. Dynamic programming solves a problem by dividing it into smaller subproblems. This is very similar to the divide-and-conquer algorithm-solving technique. The major difference, however, is that dynamic programming solves a subproblem only once.

解决这一问题的另一种方法是动态编程。动态编程通过将问题划分为更小的子问题来解决。这与分而治之的算法解决技术非常相似。但主要区别在于，动态编程只解决一次子问题。

5.1. Iterative (Bottom-Up) Approach

5.1.迭代（自下而上）法

In this approach, avoiding recursion and using an iterative process eliminates the function call overhead associated with the recursive solutions, contributing to enhanced performance:

在这种方法中，避免递归和使用迭代过程可以消除与递归解决方案相关的函数调用开销，从而提高性能：

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[i] = maxRevenue;
    }
    return dp[n];
}

Let’s test this approach as well:

我们也来测试一下这种方法：

<span class="pl-c1">@</span><span class="pl-c1"><span class="pl-token">Test</span></span><br />void givenARod_whenUsingDynamicProgramming_thenFindMaxRevenue() {
    int[] prices = {1, 5, 8, 9};
    int rodLength = 4;
    int maxRevenue = RodCuttingProblem.usingDynamicProgramming(prices, rodLength);
    assertEquals(10, maxRevenue);
}

Our dynamic programming table, represented by the dp array, stores the optimal solutions for each subproblem, where the index i corresponds to the rod length, and dp[i] holds the maximum revenue. The final entry in the dp array, dp[n], contains the maximum revenue for the original problem of a rod with length n.

我们的动态编程表由 dp 数组表示，存储了每个子问题的最优解，其中索引 i 与杆的长度相对应，dp[i] 保存了最大收益。dp数组的最后一个条目dp[n]包含长度为n的钓竿的原始问题的最大收益。

This approach is also memory-efficient as it doesn’t require an additional memoization table.

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

5.2. Unbounded Knapsack Solution

5.2.无界 Knapsack 解法

The unbounded knapsack approach is a dynamic programming technique used to solve optimization problems where an item can be chosen unlimited times. This means that the same cut length can be selected and included in the rod multiple times if it contributes to maximizing the revenue.

无界背包方法是一种动态编程技术，用于解决可无限次选择项目的优化问题。这意味着，只要有助于实现收入最大化，就可以多次选择相同的切割长度并将其纳入杆中。

Let’s take a look at the implementation:

让我们来看看实施情况：

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

Similar to the iterative (bottom-up) approach, this algorithm computes the maximum revenue for each rod length.

与迭代法（自下而上）类似，该算法计算每根杆长度的最大收益。

Let’s test this approach:

让我们来测试一下这种方法：

<span class="pl-c1">@</span><span class="pl-c1"><span class="pl-token">Test</span></span><br />void givenARod_whenUsingGreedy_thenFindMaxRevenue() {
    int[] prices = {1, 5, 8, 9};
    int rodLength = 4;
    int maxRevenue = RodCuttingProblem.usingUnboundedKnapsack(prices, rodLength);
    assertEquals(10, maxRevenue);
}

The drawback of this approach is the potential for increased space complexity. 

这种方法的缺点是可能会增加空间的复杂性。

6. Conclusion

6.结论

In this tutorial, we’ve understood the Rod Cutting Problem and discussed various ways to solve it.

在本教程中，我们了解了杆切削问题，并讨论了解决该问题的各种方法。

The recursive approach offers simplicity but suffers from exponential time complexity. The memoization method addresses this by reusing solutions and introducing slight space complexity. The iterative approach further improves efficiency, eliminating recursion overhead.

递归方法简单易行，但时间复杂度呈指数级增长。memoization 方法通过重复使用解决方案来解决这一问题，并引入了轻微的空间复杂性。迭代法进一步提高了效率，消除了递归开销。

The choice between these approaches depends on specific problem characteristics, involving trade-offs in time, space, and implementation complexity.

如何选择这些方法取决于具体的问题特征，涉及时间、空间和实施复杂性的权衡。

As always, the code used in the examples is available over on GitHub.

一如既往，示例中使用的代码可在 GitHub 上获取。