java - 棒切割 : when the rod is bigger than the array length

Question

如何修改 cutRod 和 BottomUpCutRod 方法以保存大于数组长度的长度。例如，当前 p 的长度为 11，我如何切割长度为 15、20 等的杆，并具有相同的数组。例如

p = {0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30};

如果我调用 cutRod(p,10)，我会得到 30，但它当然会在 cutRod(p,15) 或cutRod(p,20)。 (同样适用于bottomUpCutRod)。有什么想法如何做到这一点？这是动态编程问题，我实现 BottomUpCutRod 方法的想法是遍历 p 并为每个元素计算其自身及其邻居的每个排列，并在必要时更新结果数组 r。

 public class Main {    
    private static final double MINUS_INFINITY = Double.NEGATIVE_INFINITY;    

    public static void main(String[] args) {

        // price array
        double[] p = {0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30};

        // test cutRod
        cutRod(p,10);

        // test bottomUpCutRod
       bottomUpCutRod(p,10);

    }//end of main

    // an optimal cut for a rod of length n
    // p is the price array
    // use recursion
    private static double cutRod(double[] p, int value) {
        double[] r = new double[value+1];
        double out = 0;

          // initialize r to NEGATIVE_INFINITY;
        for (int i = 1; i < r.length; i++)
            r[i] = MINUS_INFINITY;

        // call the helper method
        out = helpCutRod(p,r.length-1,r);

        // print r
        System.out.println("Result ");
        System.out.println("r[" + (r.length-1) + "] = " + r[r.length-1]);

        return out;
    }//end of method             

    // helpCutRod computes an optimal cut for a rod 
    // p is the price array and r[i] is the optimal cut for a rod of length i
    // n is the length of the rod that is currently being computed

    private static double helpCutRod(double[] p, int n, double[] r) {
        double q = MINUS_INFINITY;
        if (r[n] >= 0)  // the whole r was computed
            return r[n];
        if (n == 0)
           q = 0;
        else {
            for (int i = 1; i <= n; i++) {                
                 q = RodCutting.max(q, p[i] + helpCutRod(p,n-i,r));
            }    
            r[n] = q;
        }           
        return q;
    }                

    // use the bottom-up approach
    // do NOT use recursion

    private static double bottomUpCutRod(double[] p, int len) {
        // r[i] is the optimal cut for a rod of length i
        double[] r = new double[len+1];
        r[0] = 0;
        for (int j = 1; j < p.length; j++) {

            // compute r[j]
            double q = MINUS_INFINITY;

            // r[j] is the maximum over i of p[i] + r[j-i]
            // where 1<= i <= j

            for (int i = 1; i <= j; i++)                
                q = max(q, p[i] + r[j-i]);

            // update value of r[j]
            r[j] = q;
        }//end of for outer    

        // print r 
        System.out.println("The r array from the bottomUpCutRod:");
            System.out.println("r[" + len + "] = " + r[len]);
        return r[len] ;       
    }//end of method
    public static double max(double a, double b){

        if(a<=b){
            return b;
        }else{
            return a;
        }   
    }//end of max
}//end of class

Answer 1

如果我正确理解了杆切割问题，您的价格数组 p 会告诉您可以出售长度为 0 到 p.length - 1 的杆件的价格。因此，如果数组长度为 11，即使您的初始杆长度为 15、20 或 30，您也知道长度不超过 10 的零件的价格。由于您不知道长度 11 及以上的价格，我假设您可以安全地将它们设置为 0。然后，我希望算法将您的杆切成您知道正价格的零件。

如果所有这些都是正确的，那么解决方案就很简单。例如，要计算 cutRod(p, 15)，首先执行

    p = Arrays.copyOf(p, 15 + 1);

这会将 p 复制到索引为 0 到 15 的新数组中，并用 zeore 填充。现在运行您的方法。当然，其他初始长度也类似。

通过此修改，您的程序将打印杆长度为 15:

Result 
r[15] = 43.0
The r array from the bottomUpCutRod:
r[15] = 43.0

我认为它在 10、3 和 2 处找到了碎片，产生的价格为 30 + 8 + 5 = 43，但我没有检查过。

编辑:如果杆比价格数组长很多，那么让它用比价格数组的最大值更长的切割来计算结果可能是浪费的。因此，除了上面的快速修复之外，实际上可以修改您的方法以接受较短的价格数组和较长的初始杆。

在递归helpCutRod()中，将for循环更改为:

        for (int i = 1; i <= Math.min(n, p.length - 1); i++) {                

这将确保只考虑我们有价格的作品。

对于 bottomUpCutRod()，需要进行两处更改:

第一个 for 循环需要运行，直到 j 等于 len:

    for (int j = 1; j < r.length; j++) {

再说一遍，内部 for 循环不应超出 p 的边界:

        for (int i = 1; i <= Math.min(j, p.length - 1); i++)                

通过这三个修改而不是 p 数组的扩展，程序打印与上面相同的结果。