如何修改切杆问题，使尺寸增加一个以上

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。