动态规划--杆切割自下而上算法(CLRS)解不正确？
关于“棒材切割”问题：
给定一根长度为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]...等等。这意味着在计算rx时，我们保证有RX-1。
rx表示长度为x的杆的最大值(经过切割以使利润最大化)，而px则表示长度为x的单条杆的价格。第3-8行计算j=1到n的值r[j]，第5-6行计算最大价格，通过考虑所有可能的裁剪，我们可以出售长度为j的杆。那么，在第6行中用pi代替ri又有什么意义呢?如果我们在切完一根棒子后想要找到它的最高价格= i，难道不应该加上ri和rj -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));
}
}回答 2
Stack Overflow用户
发布于 2018-10-31 21:14:05
他们应该是等价物。
CLRS方法背后的直觉是，他们试图找到单一的“最后一次切割”，假设最后一根杆的长度为i，因此具有精确的p[i]值。在这个公式中，长度i的“最后一段”不再被进一步切割，但是长度j-i的其余部分是。
您的方法考虑了所有的分裂杆分成两部分，其中每一个两个部分可以进一步切割。与CLRS方法相比，这是一组超集的案例。
这两种方法都是正确的，具有相同的渐近复杂性。但是，我认为CLRS解决方案更“规范”，因为它更符合DP解决方案的一种常见形式，在这种情况下，您只考虑最后一件“事情”(在本例中，是最后一块未切割的杆)。
Stack Overflow用户
发布于 2018-11-01 16:08:30
我想这两种方法都是正确的。
在我们证明这两种方法都是正确的之前，让我们定义一下每一种方法到底要做什么。
pi + rj -我会给你一个最大的值，你可以从一根长j的杆子上得到，而那条的尺寸是“i”(不能再除以那块了)。
ri +rj-我会给你最大的价值，你可以从杆的长度i和第一次切割的长度“i”(可以进一步分开)
现在假设我们有一个长度为x的棒，解集将包含长度为k的部分。
由于k为0
在第二种方法中，您可以在rk + rX-k中找到相同的结果，因为我们知道rk将是>= pk。
但是，在你的方法，你可以得到更快的结果(一半的时间)，因为你是从两端切割棒，所以在你的方法，你可以运行内环，一半的长度应该是好的。
但是我认为在您的代码中，内部for循环中有一个bug，应该是j >= (i / 2)而不是j >= (n / 2)。
https://stackoverflow.com/questions/53091637
复制相似问题
腾讯云开发者
