动态编程-具有最大切削量的杆切割问题和实际解决方案 - java

因此，我正在尝试为rod cutting problem的修改版本编写代码。该链接很好地说明了问题。但是，我想修改代码以不仅实际返回解决方案（即哪些割线可以提供最佳解决方案），而且还要将割线的数量限制为最大k。

为了验证概念，我正在尝试创建一种算法来实现这一目标。以下是到目前为止的内容，我认为它成功返回了实际的解决方案，但是，我不知道如何将最大值限制为k。

 let r[0..n] be a new array
 r[0] = 0
 for j = 1 to n
    q = -1
    for i = 1 to j
        for k = 0 to n-1
          q = Math.max(q[n][k], p[i] + q[n-i-1][k-1]);
    r[j] = q
 return r[n]

请不要在您的答案中提供实际的代码，我想自己实现，我只需要帮助调整我的算法以提供正确的解决方案即可。

更新1：通过向数组添加第二维，我已经能够找到最多k个切口的最佳解决方案。如上面的代码所示。

java大神给出的解决方案

就像您说的那样，您已经有了最佳的解决方案，此答案仅包括如何追溯确切的解决方案（在每个步骤中进行的切割）。

存储长度= n且最大切割= k的候选切割

为此，您只需要一个二维数组（例如visit[n][k]）来存储制作的切割，该切割将获得最大的q[n][k]解。在伪代码和递归关系方面，将如下所示。

for each value of i:
  q[n][k] = q[n][k-1]
  visit[n][k] = -1
  if q[n][k] < p[i] + q[n-i-1][k-1]:
    q[n][k] = p[i] + q[n-i-1][k-1]
    visit[n][k] = i

说明

我们可能没有使解决方案最大化的切入点。在这种情况下，我们初始化visit[n][k] = -1。
每次，我们都有一个候选人在n处切割长度为length=i+1的棒。我们可以通过切割获得更好的价格，我们将相应的切割存储在另一个二维数组中。

重构解决方案

使用此2维数组（visit[n][k]）来追溯精确的切割，可以使用以下伪代码（我故意避免使用代码，因为您提到了不需要它）。

cuts = []
while k > 0:
  i = visit[n][k]
  if i != -1
    // If there is a cut
    cuts.push(i + 1)
    n = n - i - 1
  k = k - 1

说明

我们从k迭代到0。
每次，当visit[n][k]不是-1时，即。最好在某处切割，切割后我们重新分配n，即。 n = n-i-1并将结果cut存储在数组cuts中。
最后，cuts将包含导致最佳解决方案的精确切割。

请注意，就递归关系中使用的变量而言，您的问题中存在的伪代码有些不正确。 q用于存储DP 2-d数组和整数-1。自下而上的DP完全不使用j，并用常量n代替。 q[j][k]未初始化。但是，总体思路是正确的。

java:继承 - java

有哪些替代继承的方法？ java大神给出的解决方案 有效的Java：偏重于继承而不是继承。 （这实际上也来自“四人帮”）。他提出的理由是，如果扩展类未明确设计为继承，则继承会引起很多不正常的副作用。例如，对super.someMethod()的任何调用都可以引导您通过未知代码的意外路径。取而代之的是，持有对本来应该扩展的类的引用，然后委托给它。这是与Eric…

Java-如何将此字符串转换为日期？ - java

我从服务器收到此消息，我不明白T和Z的含义，2012-08-24T09:59:59Z将此字符串转换为Date对象的正确SimpleDateFormat模式是什么？ java大神给出的解决方案 这是ISO 8601标准。您可以使用SimpleDateFormat simpleFormat = new SimpleDateFormat("yyyy-MM…

从方法返回数组-Java - java

private static Coordinate[] getCircleCoordintaes() { Coordinate coordinates[] = {new Coordinate(0, 0)}; return coordinates; } 以上程序工作正常。在上面的程序中，返回的坐标数组首先初始化了数组使用这条线Coordinate coordi…

Java Swing SearchBox模型 - java

我需要使用Java Swing的搜索框，如果单击任何建议，当输入字母时它将显示来自数据库的建议，它将执行一些操作。如果有可能在Java swing中，请提供源代码提前致谢 java大神给出的解决方案 您可以使用DefaultComboBoxModel，输出将是这样。Try this在此代码中，您将找到countries数组，因此您需要从数据库中获取此数组。

JAVA:如何检查对象数组中的所有对象是否都是子类的对象？ - java

我有一个对象数组。现在，我要检查所有这些对象是否都是MyObject的实例。有没有比这更好的选择：boolean check = true; for (Object o : justAList){ if (!(o instanceof MyObject)){ check = false; break; } } java大神给出的解决方案 如果您不喜欢循环，则…