给定一根长度为n英寸的杆，以及一系列价格，其中包括所有小于n尺寸的杆件的价格。通过切割杆件并出售这些杆件来确定可获得的最大价值。例如，如果杆的长度为8，不同工件的值如下所示，则可获得的最大值为22（通过切割长度为2和6的两个工件）
null
length | 1 2 3 4 5 6 7 8 --------------------------------------------price | 1 5 8 9 10 17 17 20
如果价格如下所示，则最大可获得价值为24（通过切割八片长度1）
length | 1 2 3 4 5 6 7 8 --------------------------------------------price | 3 5 8 9 10 17 17 20
解决这个问题的一个简单方法是生成不同部件的所有配置，并找到价格最高的配置。这个解决方案的时间复杂度是指数的。让我们看看这个问题如何既具有动态规划（DP）问题的重要性质，又可以使用动态规划有效地解决。 1） 最佳子结构： 我们可以通过在不同位置进行切割并比较切割后获得的值来获得最佳价格。对于切割后获得的工件，我们可以递归调用相同的函数。 对于长度为n的杆，让cutRod（n）为所需的（尽可能最好的价格）值。cutRod（n）可写为：。 对于{0,1..n-1}中的所有i，截杆（n）=max（价格[i]+截杆（n-i-1）） 2） 重叠子问题 以下是棒料切割问题的简单递归实现。
实现简单地遵循上面提到的递归结构。
输出
Maximum Obtainable Value is 22
考虑到上述实现，下面是长度为4的杆的递归树。
cR() ---> cutRod() cR(4) / / / / cR(3) cR(2) cR(1) cR(0) / | / | / | / | cR(2) cR(1) cR(0) cR(1) cR(0) cR(0) / | | / | | cR(1) cR(0) cR(0) cR(0) / /CR(0)
在上述部分递归树中，cR（2）被求解两次。我们可以看到，有许多子问题被一次又一次地解决。由于再次调用相同的子问题，此问题具有重叠子问题属性。因此，杆切割问题具有两个属性（参见 这 和 这 )一个动态规划问题。像其他典型的 动态规划问题 ，通过以自下而上的方式构造临时数组val[]可以避免相同子问题的重新计算。
C++
// A Dynamic Programming solution for Rod cutting problem #include<iostream> #include <bits/stdc++.h> #include<math.h> using namespace std; // A utility function to get the maximum of two integers int max( int a, int b) { return (a > b)? a : b;} /* Returns the best obtainable price for a rod of length n and price[] as prices of different pieces */ int cutRod( int price[], int n) { int val[n+1]; val[0] = 0; int i, j; // Build the table val[] in bottom up manner and return the last entry // from the table for (i = 1; i<=n; i++) { int max_val = INT_MIN; for (j = 0; j < i; j++) max_val = max(max_val, price[j] + val[i-j-1]); val[i] = max_val; } return val[n]; } /* Driver program to test above functions */ int main() { int arr[] = {1, 5, 8, 9, 10, 17, 17, 20}; int size = sizeof (arr)/ sizeof (arr[0]); cout << "Maximum Obtainable Value is " <<cutRod(arr, size); getchar (); return 0; } // This code is contributed by shivanisinghss2110 |
C
// A Dynamic Programming solution for Rod cutting problem #include<stdio.h> #include<limits.h> // A utility function to get the maximum of two integers int max( int a, int b) { return (a > b)? a : b;} /* Returns the best obtainable price for a rod of length n and price[] as prices of different pieces */ int cutRod( int price[], int n) { int val[n+1]; val[0] = 0; int i, j; // Build the table val[] in bottom up manner and return the last entry // from the table for (i = 1; i<=n; i++) { int max_val = INT_MIN; for (j = 0; j < i; j++) max_val = max(max_val, price[j] + val[i-j-1]); val[i] = max_val; } return val[n]; } /* Driver program to test above functions */ int main() { int arr[] = {1, 5, 8, 9, 10, 17, 17, 20}; int size = sizeof (arr)/ sizeof (arr[0]); printf ( "Maximum Obtainable Value is %d" , cutRod(arr, size)); getchar (); return 0; } |
JAVA
// A Dynamic Programming solution for Rod cutting problem class RodCutting { /* Returns the best obtainable price for a rod of length n and price[] as prices of different pieces */ static int cutRod( int price[], int n) { int val[] = new int [n+ 1 ]; val[ 0 ] = 0 ; // Build the table val[] in bottom up manner and return // the last entry from the table for ( int i = 1 ; i<=n; i++) { int 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]; } /* Driver program to test above functions */ public static void main(String args[]) { int arr[] = new int [] { 1 , 5 , 8 , 9 , 10 , 17 , 17 , 20 }; int size = arr.length; System.out.println( "Maximum Obtainable Value is " + cutRod(arr, size)); } } /* This code is contributed by Rajat Mishra */ |
python
# A Dynamic Programming solution for Rod cutting problem INT_MIN = - 32767 # Returns the best obtainable price for a rod of length n and # price[] as prices of different pieces def cutRod(price, n): val = [ 0 for x in range (n + 1 )] val[ 0 ] = 0 # Build the table val[] in bottom up manner and return # the last entry from the table for i in range ( 1 , n + 1 ): max_val = INT_MIN for j in range (i): max_val = max (max_val, price[j] + val[i - j - 1 ]) val[i] = max_val return val[n] # Driver program to test above functions arr = [ 1 , 5 , 8 , 9 , 10 , 17 , 17 , 20 ] size = len (arr) print ( "Maximum Obtainable Value is " + str (cutRod(arr, size))) # This code is contributed by Bhavya Jain |
C#
// A Dynamic Programming solution // for Rod cutting problem using System; class GFG { /* Returns the best obtainable price for a rod of length n and price[] as prices of different pieces */ static int cutRod( int []price, int n) { int []val = new int [n + 1]; val[0] = 0; // Build the table val[] in // bottom up manner and return // the last entry from the table for ( int i = 1; i<=n; i++) { int max_val = int .MinValue; 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]; } // Driver Code public static void Main() { int []arr = new int [] {1, 5, 8, 9, 10, 17, 17, 20}; int size = arr.Length; Console.WriteLine( "Maximum Obtainable Value is " + cutRod(arr, size)); } } // This code is contributed by Sam007 |
PHP
<?php // A Dynamic Programming solution for // Rod cutting problem /* Returns the best obtainable price for a rod of length n and price[] as prices of different pieces */ function cutRod( $price , $n ) { $val = array (); $val [0] = 0; $i ; $j ; // Build the table val[] in bottom // up manner and return the last // entry from the table for ( $i = 1; $i <= $n ; $i ++) { $max_val = PHP_INT_MIN; for ( $j = 0; $j < $i ; $j ++) $max_val = max( $max_val , $price [ $j ] + $val [ $i - $j -1]); $val [ $i ] = $max_val ; } return $val [ $n ]; } // Driver program to test above functions $arr = array (1, 5, 8, 9, 10, 17, 17, 20); $size = count ( $arr ); echo "Maximum Obtainable Value is " , cutRod( $arr , $size ); // This code is contributed by anuj_67. ?> |
Javascript
<script> // A Dynamic Programming solution // for Rod cutting problem /* Returns the best obtainable price for a rod of length n and price[] as prices of different pieces */ function cutRod(price, n) { let val = new Array(n + 1); val[0] = 0; // Build the table val[] in // bottom up manner and return // the last entry from the table for (let i = 1; i<=n; i++) { let max_val = Number.MIN_VALUE; for (let j = 0; j < i; j++) max_val = Math.max(max_val, price[j] + val[i - j - 1]); val[i] = max_val; } return val[n]; } let arr = [1, 5, 8, 9, 10, 17, 17, 20]; let size = arr.length; document.write( "Maximum Obtainable Value is " + cutRod(arr, size) + "n" ); </script> |
输出
Maximum Obtainable Value is 22
上述实现的时间复杂度为O（n^2），这比朴素递归实现的最坏情况下的时间复杂度要好得多。
3） 使用无界背包的想法。
这个问题与无界背包问题非常相似，在无界背包问题中，同一物品多次出现。这是杆子的碎片。
现在我将在无界背包和棒切割问题之间建立一个类比。
![图片[1]-切割杆| DP-13-yiteyi-C++库](https://www.yiteyi.com/wp-content/uploads/geeks/20201014/geeks_Untitleddrawing-300x225.png)
C++
// CPP program for above approach #include <iostream> using namespace std; // Global Array for // the purpose of memoization. int t[9][9]; // A recursive program, using , // memoization, to implement the // rod cutting problem(Top-Down). int un_kp( int price[], int length[], int Max_len, int n) { // The maximum price will be zero, // when either the length of the rod // is zero or price is zero. if (n == 0 || Max_len == 0) { return 0; } // If the length of the rod is less // than the maximum length, Max_lene will // consider it.Now depending // upon the profit, // either Max_lene we will take // it or discard it. if (length[n - 1] <= Max_len) { t[n][Max_len] = max(price[n - 1] + un_kp(price, length, Max_len - length[n - 1], n), un_kp(price, length, Max_len, n - 1)); } // If the length of the rod is // greater than the permitted size, // Max_len we will not consider it. else { t[n][Max_len] = un_kp(price, length, Max_len, n - 1); } // Max_lene Max_lenill return the maximum // value obtained, Max_lenhich is present // at the nth roMax_len and Max_lenth column. return t[n][Max_len]; } /* Driver program to test above functions */ int main() { int price[] = { 1, 5, 8, 9, 10, 17, 17, 20 }; int n = sizeof (price) / sizeof (price[0]); int length[n]; for ( int i = 0; i < n; i++) { length[i] = i + 1; } int Max_len = n; // Function Call cout << "Maximum obtained value is " << un_kp(price, length, n, Max_len) << endl; } |
C
// C program for above approach #include <stdio.h> #include <stdlib.h> int max( int a, int b) { return (a > b) ? a : b; } // Global Array for the // purpose of memoization. int t[9][9]; // A recursive program, using , // memoization, to implement the // rod cutting problem(Top-Down). int un_kp( int price[], int length[], int Max_len, int n) { // The maximum price will be zero, // when either the length of the rod // is zero or price is zero. if (n == 0 || Max_len == 0) { return 0; } // If the length of the rod is less // than the maximum length, Max_lene // will consider it.Now depending // upon the profit, // either Max_lene we will take it // or discard it. if (length[n - 1] <= Max_len) { t[n][Max_len] = max(price[n - 1] + un_kp(price, length, Max_len - length[n - 1], n), un_kp(price, length, Max_len, n - 1)); } // If the length of the rod is greater // than the permitted size, Max_len // we will not consider it. else { t[n][Max_len] = un_kp(price, length, Max_len, n - 1); } // Max_lene Max_lenill return // the maximum value obtained, // Max_lenhich is present at the // nth roMax_len and Max_lenth column. return t[n][Max_len]; } /* Driver program to test above functions */ int main() { int price[] = { 1, 5, 8, 9, 10, 17, 17, 20 }; int n = sizeof (price) / sizeof (price[0]); int length[n]; for ( int i = 0; i < n; i++) { length[i] = i + 1; } int Max_len = n; // Function Call printf ( "Maximum obtained value is %d " , un_kp(price, length, n, Max_len)); } |
JAVA
// Java program for above approach import java.io.*; class GFG { // Global Array for // the purpose of memoization. static int t[][] = new int [ 9 ][ 9 ]; // A recursive program, using , // memoization, to implement the // rod cutting problem(Top-Down). public static int un_kp( int price[], int length[], int Max_len, int n) { // The maximum price will be zero, // when either the length of the rod // is zero or price is zero. if (n == 0 || Max_len == 0 ) { return 0 ; } // If the length of the rod is less // than the maximum length, Max_lene will // consider it.Now depending // upon the profit, // either Max_lene we will take // it or discard it. if (length[n - 1 ] <= Max_len) { t[n][Max_len] = Math.max( price[n - 1 ] + un_kp(price, length, Max_len - length[n - 1 ], n), un_kp(price, length, Max_len, n - 1 )); } // If the length of the rod is // greater than the permitted size, // Max_len we will not consider it. else { t[n][Max_len] = un_kp(price, length, Max_len, n - 1 ); } // Max_lene Max_lenill return the maximum // value obtained, Max_lenhich is present // at the nth roMax_len and Max_lenth column. return t[n][Max_len]; } public static void main(String[] args) { int price[] = new int [] { 1 , 5 , 8 , 9 , 10 , 17 , 17 , 20 }; int n = price.length; int length[] = new int [n]; for ( int i = 0 ; i < n; i++) { length[i] = i + 1 ; } int Max_len = n; System.out.println( "Maximum obtained value is " + un_kp(price, length, n, Max_len)); } } // This code is contributed by rajsanghavi9. |
Python3
# Python program for above approach # Global Array for # the purpose of memoization. t = [[ 0 for i in range ( 9 )] for j in range ( 9 )] # A recursive program, using , # memoization, to implement the # rod cutting problem(Top-Down). def un_kp(price, length, Max_len, n): # The maximum price will be zero, # when either the length of the rod # is zero or price is zero. if (n = = 0 or Max_len = = 0 ): return 0 ; # If the length of the rod is less # than the maximum length, Max_lene will # consider it.Now depending # upon the profit, # either Max_lene we will take # it or discard it. if (length[n - 1 ] < = Max_len): t[n][Max_len] = max (price[n - 1 ] + un_kp(price, length, Max_len - length[n - 1 ], n), un_kp(price, length, Max_len, n - 1 )); # If the length of the rod is # greater than the permitted size, # Max_len we will not consider it. else : t[n][Max_len] = un_kp(price, length, Max_len, n - 1 ); # Max_lene Max_lenill return the maximum # value obtained, Max_lenhich is present # at the nth roMax_len and Max_lenth column. return t[n][Max_len]; if __name__ = = '__main__' : price = [ 1 , 5 , 8 , 9 , 10 , 17 , 17 , 20 ]; n = len (price); length = [ 0 ] * n; for i in range (n): length[i] = i + 1 ; Max_len = n; print ( "Maximum obtained value is " ,un_kp(price, length, n, Max_len)); # This code is contributed by gauravrajput1 |
C#
// C# program for above approach using System; public class GFG { // Global Array for // the purpose of memoization. static int [,]t = new int [9,9]; // A recursive program, using , // memoization, to implement the // rod cutting problem(Top-Down). public static int un_kp( int []price, int []length, int Max_len, int n) { // The maximum price will be zero, // when either the length of the rod // is zero or price is zero. if (n == 0 || Max_len == 0) { return 0; } // If the length of the rod is less // than the maximum length, Max_lene will // consider it.Now depending // upon the profit, // either Max_lene we will take // it or discard it. if (length[n - 1] <= Max_len) { t[n,Max_len] = Math.Max(price[n - 1] + un_kp(price, length, Max_len - length[n - 1], n), un_kp(price, length, Max_len, n - 1)); } // If the length of the rod is // greater than the permitted size, // Max_len we will not consider it. else { t[n,Max_len] = un_kp(price, length, Max_len, n - 1); } // Max_lene Max_lenill return the maximum // value obtained, Max_lenhich is present // at the nth roMax_len and Max_lenth column. return t[n,Max_len]; } // Driver code public static void Main(String[] args) { int []price = new int [] { 1, 5, 8, 9, 10, 17, 17, 20 }; int n = price.Length; int []length = new int [n]; for ( int i = 0; i < n; i++) { length[i] = i + 1; } int Max_len = n; Console.WriteLine( "Maximum obtained value is " + un_kp(price, length, n, Max_len)); } } // This code is contributed by gauravrajput1. |
Javascript
<script> // Javascript program for above approach // Global Array for // the purpose of memoization. let t = new Array(9); for ( var i = 0; i < t.length; i++) { t[i] = new Array(2); } // A recursive program, using , // memoization, to implement the // rod cutting problem(Top-Down). function un_kp(price, length, Max_len, n) { // The maximum price will be zero, // when either the length of the rod // is zero or price is zero. if (n == 0 || Max_len == 0) { return 0; } // If the length of the rod is less // than the maximum length, Max_lene will // consider it.Now depending // upon the profit, // either Max_lene we will take // it or discard it. if (length[n - 1] <= Max_len) { t[n][Max_len] = Math.max(price[n - 1] + un_kp(price, length, Max_len - length[n - 1], n), un_kp(price, length, Max_len, n - 1)); } // If the length of the rod is // greater than the permitted size, // Max_len we will not consider it. else { t[n][Max_len] = un_kp(price, length, Max_len, n - 1); } // Max_lene Max_lenill return the maximum // value obtained, Max_lenhich is present // at the nth roMax_len and Max_lenth column. return t[n][Max_len]; } // Driver code let price = [ 1, 5, 8, 9, 10, 17, 17, 20 ]; let n = price.length; let length = Array(n).fill(0); for (let i = 0; i < n; i++) { length[i] = i + 1; } let Max_len = n; // Function Call document.write( "Maximum obtained value is " + un_kp(price, length, n, Max_len)); </script> |
输出
Maximum obtained value is 22
![图片[2]-切割杆| DP-13-yiteyi-C++库](https://www.yiteyi.com/wp-content/uploads/geeks/20210513/geeks_Screenshot69-200x29.png)
如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
