3

对于“切杆”问题：

给定一根长度为 n 英寸的杆和一个价格数组，其中包含所有尺寸小于 n 的块的价格。确定通过切割杆并出售碎片可获得的最大值。[链接]

算法简介(CLRS) 第 366 页给出了这种自下而上（动态编程）方法的伪代码：

1. BOTTOM-UP-CUT-ROD(p, n)              
2. let r[0 to n]be a new array .        
3. r[0] = 0                             
4. for j = 1 to n                       
5.     q = -infinity                    
6.     for i = 1 to j                   
7.         q = max(q, p[i] + r[j - i])  
8.     r[j] = q                         
9. return r[n]

现在，我无法理解第 6 行背后的逻辑。为什么他们这样做max(q, p[i] + r[j - i])而不是max(q, r[i] + r[j - i])？由于这是一种自下而上的方法，我们将r[1]先计算，然后再r[2], r[3]...进行计算。这意味着在计算 r[x] 时，我们保证有 r[x - 1]。

r[x] 表示我们可以获得长度为 x 的杆的最大值（在将其切割以最大化利润之后），而 p[x] 表示长度为 x 的单根杆的价格。第 3 - 8 行计算r[j]j = 1 到 n 的值，第 5 - 6 行计算通过考虑所有可能的切割，我们可以卖出长度为 j 的杆的最高价格。那么，在第 6 行中使用 p[i] 而不是 r[i] 有什么意义呢？如果在我们将长度 = i 切割后试图找到一根杆的最高价格，我们不应该添加价格吗？ r[i] 和 r[j - 1]？

我已经使用此逻辑编写了 Java 代码，并且它似乎为我尝试过的许多测试用例提供了正确的输出。我是否错过了一些我的代码产生错误/低效解决方案的情况？请帮帮我。谢谢！

class Solution {
    private static int cost(int[] prices, int n) {
        if (n == 0) {
            return 0;
        }

        int[] maxPrice = new int[n];

        for (int i = 0; i < n; i++) {
            maxPrice[i] = -1;
        }

        for (int i = 1; i <= n; i++) {
            int q = Integer.MIN_VALUE;

            if (i <= prices.length) {
                q = prices[i - 1];
            }

            for (int j = i - 1; j >= (n / 2); j--) {
                q = Math.max(q, maxPrice[j - 1] + maxPrice[i - j - 1]);
            }

            maxPrice[i - 1] = q;
        }

        return maxPrice[n - 1];
    }


    public static void main(String[] args) {
       int[] prices = {1, 5, 8, 9, 10, 17, 17, 20};

        System.out.println(cost(prices, 8));
    }
}
4

2 回答 2

3

它们应该是等价的。

CLRS 方法背后的直觉是，他们试图找到单个“最后切割”，假设最后一根杆有长度i，因此具有精确的值p[i]。在这个公式中，“最后一段”长度i没有被进一步切割，但剩余的长度j-i被切割。

您的方法将杆的所有分裂视为两部分，其中两部分中的每一个都可以进一步切割。与 CLRS 方法相比，这考虑了案例的超集。

这两种方法都是正确的，并且具有相同的渐近复杂度。但是，我认为 CLRS 解决方案更“规范”，因为它更接近于 DP 解决方案的常见形式，您只考虑最后一个“事物”（在这种情况下，是最后一块未切割的杆）。

于 2018-10-31T21:14:05.133 回答
0

我想这两种方法都是正确的。

在我们证明它们都是正确的之前，让我们定义每种方法的确切作用

p[i] + r[j - i] 将为您提供您可以从长度为 j 的杆中获得的最大值，并且该部分的大小为“i”（不能进一步划分该部分）

r[i] + r[ji] 将为您提供您可以从长度为 i 的杆中获得的最大值，并且第一次切割的长度为“i”（可以进一步划分两个部分）

现在考虑我们有一根长度为 X 的杆，解决方案集将包含长度为 k 的块

并且由于 k 是 0 < k < X 您将在第一种方法中找到 p[k] + r[Xk] 处的最大值

在第二种方法中，您可以使用 r[k] + r[Xk] 找到相同的结果，因为我们知道 r[k] 将 >= p[k]

但是在您接近时，您可以获得更快的结果（一半时间），因为您从两端切割杆，所以在您接近时，您可以将内环运行一半的长度应该是好的。

但是我认为在您的代码中，内部 for 循环中有一个错误，它应该是 j >= (i / 2) 而不是 j >= (n / 2)

于 2018-11-01T16:08:30.143 回答