java - 如何修改 Rod-Cutting 问题以采用增加超过 1 的尺寸

Question

这是经典的杆切割问题的代码。正如代码所示，大小为 1、2、3 和 4，即价格数组 arr[] 的大小。我将如何修改代码，以便将大小设置为与给定值不同的值。例如，改为 1、2、3 和 5。

 static double cutRod(double price[],int n) 
 { 
     double val[] = new double[n+1]; 
     val[0] = 0; 

     for (int i = 1; i<=n; i++) 
     { 
         double max_val = Integer.MIN_VALUE; 
         for (int j = 0; j < i; j++) 
             max_val = Math.max(max_val,  
                                price[j] + val[i-j-1]); 
         val[i] = max_val; 
     } 

     return val[n]; 
 } 

  public static void main(String args[]) 
 { 
     double arr[] = new double[] {1.2, 3, 5.8, 10.1}; 
     int size = arr.length; 
     System.out.println("Maximum Obtainable Value is " + 
                         cutRod(arr, size)); 
 } 
}

Answer 1

在经典问题中，内部循环中的 j+1 表示可能的分割大小。如果您有自定义切割尺寸，请将它们存储在数组中并使用它们代替 j + 1。

在上面的程序中，令custom_sizes 为存储切割的数组，例如。 1,2,3,5 等

修改上述程序:

 static double cutRod(double price[],int custom_sizes[], int n) 
 { 
   double val[] = new double[n+1]; 
   val[0] = 0; 

   for (int i = 1; i<=n; i++) 
   { 
       double max_val = Integer.MIN_VALUE; 
       for (int j = 0; j < custom_sizes.length; j++) {
           if (i - custom_sizes[j] >= 0)
             max_val = Math.max(max_val,  
                                price[j] + val[i-custom_sizes[j]]); 
       }
       val[i] = max_val; 
   } 
   return val[n];
} 

请注意，假设输入是有效的，并且 price 和 custom_sizes 的长度相等 = n。