给定一根长度为L的杆，任务是以这样的方式切割杆，使长度为p、q和r的段的总数最大化。这些线段的长度只能为p、q和r。
null
例如：
输入： l=11，p=2，q=3，r=5 输出： 5. 第2、2、2、2和3段
输入： l=7，p=2，q=5，r=5 输出： 2. 第2段和第5段
方法1：
这可以被视为一个经典的递归问题，它进一步缩小到 回忆录 （自上而下）方法 动态规划 .最初，我们有长度 L 现在，我们有三种尺寸可供选择，或者我们可以切割长度 P 或 Q 或 R .比方说我们切了一段 P ，所以剩下的长度是 l-p 同样的，还有削减 Q & R 导致剩余长度 l-q & l-r 分别地我们将为剩余的长度调用递归函数，在任何后续实例中，我们将有这三个选择。我们将存储所有这些递归调用的答案，并从中取最大值+1，因为在任何情况下，我们也将从这个特定调用中取1。另外，请注意，当且仅当可用长度大于我们想要剪切的长度（即假设长度）时，才会进行递归调用 p=3 ，在某些递归调用之后，可用的长度仅为2，因此我们不能将这一行的长度缩短为 P 不再
下面是 伪码 同样地：
if(l==0) // Base Case return 0; int a,b,c;if(p<=l) a=func(l-p,p,q,r);if(q<=l) b=func(l-q,p,q,r);if(r<=l) c=func(l-r,p,q,r);return 1+max({a,b,c});
下面是的递归树 l=4，p=2，q=1，r=1 :
![图片[1]-最大化长度为p、q和r的分段数-yiteyi-C++库](https://www.yiteyi.com/wp-content/uploads/geeks/20211128/geeks_MaximizeSegmentsRecursionTree.jpg)
l=4，p=2，q=1和r=1的递归树
我们可以清楚地观察到，在每次调用时，给定的长度（最初为4）被分为3个不同的子部分。此外，我们可以看到，递归正在对某些条目进行重复( 红色 箭头代表了对 l=2，黄色 对于 l=3 和 蓝色 对于 l=1）。 因此，我们可以 回忆 结果会出现在任何容器或数组中，因此可以避免重复相同的递归调用。
现在，上面 伪码 更改：
vector<int> dp(10005,-1); // Initialise DP Table ( Array can also be used )if(l==0) // Base Case return 0; if(dp[l]!=-1) // If already memoized , return from here only return dp[l];int a,b,c;if(p<=l) a=func(l-p,p,q,r);if(q<=l) b=func(l-q,p,q,r);if(r<=l) c=func(l-r,p,q,r); return dp[l]=1+max({a,b,c}); // Memoize the result in the dp table & return
现在，让我们按照代码来实现上述代码：
C++
//C++ Code to find maximum number of cut segments // Memoization DP #include <bits/stdc++.h> using namespace std; //Function to find the maximum number of cuts. int dp[10005]; int func( int l, int p, int q, int r) { if (l==0) return 0; // Base Case if (dp[l]!=-1) // If already memoized return dp[l]; int a(INT_MIN),b(INT_MIN),c(INT_MIN); // Intitialise a,b,& c with INT_MIN if (p<=l) // If Possible to make a cut of length p a=func(l-p,p,q,r); if (q<=l) // If possible to make a cut of length q b=func(l-q,p,q,r); if (r<=l) // If possible to make a cut of length r c=func(l-r,p,q,r); return dp[l]=1+max({a,b,c}); // Memoize & return } int maximizeTheCuts( int l, int p, int q, int r) { memset (dp,-1, sizeof (dp)); // Set Lookup table to -1 int ans=func(l,p,q,r); // Utility function call if (ans<0) return 0; // If returned answer is negative , that means cuts are not possible return ans; } int main() { int l,p,q,r; cout<< "ENTER THE LENGTH OF THE ROD " <<endl; cin>>l; cout<< "ENTER THE VALUES OF p,q & r " <<endl; cin>>p>>q>>r; cout<< "THE MAXIMUM NUMBER OF SEGMENTS THAT CAN BE CUT OF LENGTH p,q & r FROM A ROD OF LENGTH l are " <<maximizeTheCuts(l,p,q,r)<<endl; return 0; } |
时间复杂性 : O（n） 其中n是必须切割的杆或线段的长度。
空间复杂性 : O（n） 其中n是必须切割的杆或线段的长度。
方法2：
由于在给定长度内可进行的最大切割次数的解决方案取决于之前在较短长度内进行的最大切割次数，这个问题可以通过动态规划方法解决。假设给我们一个 长度’l’ .用于查找可在中进行的最大切割次数 长度’l’ ，查找在较短时间内进行的切割次数 长度“l-p”， “l-q”， “l-r” 长度分别为。必要的答案是 最大值（l-p，l-q，l-r）+1 因为在这之后还需要一次切割来切割 长度’l’ 为了解决给定长度下的这个问题，求出长度上的最大切割次数 从“1”到“l” .
例子：
l=11，p=2，q=3，r=5 分析从1到11的长度：
- 无法剪切->0
- 可能的切割长度为2->1（2）
- 可能的切割长度为3->1（3）
- 可能的切割长度最大（arr[4-2]，arr[4-3]）+1->2（2,2）
- 可能的切割长度最大（arr[5-2]，arr[5-3]）+1->2（2,3）
- 可能的切割长度最大（arr[6-2]、arr[6-3]、arr[6-5]）+1->3（2,2,2）
- 可能的切割长度为最大（arr[7-2]、arr[7-3]、arr[7-5]）+1->3（2,3,2）或（2,2,3）
- 可能的切割长度最大（arr[8-2]、arr[8-3]、arr[8-5]）+1->4（2,2,2,2）
- 可能的切割长度最大为（arr[9-2]、arr[9-3]、arr[9-5]）+1->4（2,3,2,2）或（2,2,3,2）或（2,2,2,3）
- 可能的切割长度最大（arr[10-2]、arr[10-3]、arr[10-5]）+1->5（2,2,2,2,2）
- 可能的切割长度最大为（arr[11-2]、arr[11-3]、arr[11-5]）+1->5（2,3,2,2,2）或（2,2,3,2,2）或（2,2,2,3,2）或（2,2,2,2,2,3,2）或（2,2,2,3,3）
算法：
- 初始化一个 数组DP[]={-1}和DP[0]=0 .
- 运行从“1”到“l”的循环
- 如果DP[i]=-1意味着不可能使用给定的段p、q、r来划分它，那么继续；
- DP[i+p]=max（DP[i+p]，DP[i]+1）
- DP[i+q]=最大值（DP[i+q]，DP[i]+1）
- DP[i+r]=最大值（DP[i+r]，DP[i]+1）
- 打印DP[l]
伪代码：
DP[l+1]={-1}DP[0]=0for(i from 0 to l) if(DP[i]==-1) continue DP[i+p]=max(DP[i+p],DP[i]+1) DP[i+q]=max(DP[i+q],DP[i]+1) DP[i+r]=max(DP[i+r],DP[i]+1)print(DP[l])
实施：
C++
// C++ program to maximize the number // of segments of length p, q and r #include <bits/stdc++.h> using namespace std; // Function that returns the maximum number // of segments possible int findMaximum( int l, int p, int q, int r) { // Array to store the cut at each length int dp[l + 1]; // All values with -1 memset (dp, -1, sizeof (dp)); // if length of rod is 0 then total cuts will be 0 // so, initialize the dp[0] with 0 dp[0] = 0; for ( int i = 0; i <= l; i++) { // if certain length is not possible if (dp[i] == -1) continue ; // if a segment of p is possible if (i + p <= l) dp[i + p] = max(dp[i + p], dp[i] + 1); // if a segment of q is possible if (i + q <= l) dp[i + q] = max(dp[i + q], dp[i] + 1); // if a segment of r is possible if (i + r <= l) dp[i + r] = max(dp[i + r], dp[i] + 1); } // if no segment can be cut then return 0 if (dp[l] == -1) { dp[l] = 0; } // return value corresponding to length l return dp[l]; } // Driver Code int main() { int l = 11, p = 2, q = 3, r = 5; // Calling Function int ans = findMaximum(l, p, q, r); cout << ans; return 0; } |
JAVA
// Java program to maximize // the number of segments // of length p, q and r import java.io.*; class GFG { // Function that returns // the maximum number // of segments possible static int findMaximum( int l, int p, int q, int r) { // Array to store the // cut at each length int dp[] = new int [l + 1 ]; // All values with -1 for ( int i = 0 ; i < l + 1 ; i++) dp[i] = - 1 ; // if length of rod is 0 // then total cuts will // be 0 so, initialize // the dp[0] with 0 dp[ 0 ] = 0 ; for ( int i = 0 ; i <= l; i++) { // if certain length // is not possible if (dp[i] == - 1 ) continue ; // if a segment of // p is possible if (i + p <= l) dp[i + p] = Math.max(dp[i + p], dp[i] + 1 ); // if a segment of // q is possible if (i + q <= l) dp[i + q] = Math.max(dp[i + q], dp[i] + 1 ); // if a segment of // r is possible if (i + r <= l) dp[i + r] = Math.max(dp[i + r], dp[i] + 1 ); } // if no segment can be cut then return 0 if (dp[l] == - 1 ) { dp[l] = 0 ; } // return value corresponding // to length l return dp[l]; } // Driver Code public static void main(String[] args) { int l = 11 , p = 2 , q = 3 , r = 5 ; // Calling Function int ans = findMaximum(l, p, q, r); System.out.println(ans); } } // This code is contributed // by anuj_67. |
Python3
# Python 3 program to # maximize the number # of segments of length # p, q and r # Function that returns # the maximum number # of segments possible def findMaximum(l, p, q, r): # Array to store the cut # at each length # All values with -1 dp = [ - 1 ] * (l + 1 ) # if length of rod is 0 then # total cuts will be 0 # so, initialize the dp[0] with 0 dp[ 0 ] = 0 for i in range (l + 1 ): # if certain length is not # possible if (dp[i] = = - 1 ): continue # if a segment of p is possible if (i + p < = l): dp[i + p] = ( max (dp[i + p], dp[i] + 1 )) # if a segment of q is possible if (i + q < = l): dp[i + q] = ( max (dp[i + q], dp[i] + 1 )) # if a segment of r is possible if (i + r < = l): dp[i + r] = ( max (dp[i + r], dp[i] + 1 )) # if no segment can be cut then return 0 if dp[l] = = - 1 : dp[l] = 0 # return value corresponding # to length l return dp[l] # Driver Code if __name__ = = "__main__" : l = 11 p = 2 q = 3 r = 5 # Calling Function ans = findMaximum(l, p, q, r) print (ans) # This code is contributed by # ChitraNayal |
C#
// C# program to maximize // the number of segments // of length p, q and r using System; class GFG { // Function that returns // the maximum number // of segments possible static int findMaximum( int l, int p, int q, int r) { // Array to store the // cut at each length int [] dp = new int [l + 1]; // All values with -1 for ( int i = 0; i < l + 1; i++) dp[i] = -1; // if length of rod is 0 // then total cuts will // be 0 so, initialize // the dp[0] with 0 dp[0] = 0; for ( int i = 0; i <= l; i++) { // if certain length // is not possible if (dp[i] == -1) continue ; // if a segment of // p is possible if (i + p <= l) dp[i + p] = Math.Max(dp[i + p], dp[i] + 1); // if a segment of // q is possible if (i + q <= l) dp[i + q] = Math.Max(dp[i + q], dp[i] + 1); // if a segment of // r is possible if (i + r <= l) dp[i + r] = Math.Max(dp[i + r], dp[i] + 1); } // if no segment can be cut then return 0 if (dp[l] == -1) { dp[l] = 0; } // return value corresponding // to length l return dp[l]; } // Driver Code public static void Main() { int l = 11, p = 2, q = 3, r = 5; // Calling Function int ans = findMaximum(l, p, q, r); Console.WriteLine(ans); } } // This code is contributed // by anuj_67. |
Javascript
<script> // Javascript program to maximize // the number of segments // of length p, q and r // Function that returns // the maximum number // of segments possible function findMaximum(l,p,q,r) { // Array to store the // cut at each length let dp = new Array(l + 1); // All values with -1 for (let i = 0; i < l + 1; i++) dp[i] = -1; // if length of rod is 0 // then total cuts will // be 0 so, initialize // the dp[0] with 0 dp[0] = 0; for (let i = 0; i <= l; i++) { // if certain length // is not possible if (dp[i] == -1) continue ; // if a segment of // p is possible if (i + p <= l) dp[i + p] = Math.max(dp[i + p], dp[i] + 1); // if a segment of // q is possible if (i + q <= l) dp[i + q] = Math.max(dp[i + q], dp[i] + 1); // if a segment of // r is possible if (i + r <= l) dp[i + r] = Math.max(dp[i + r], dp[i] + 1); } // if no segment can be cut then return 0 if (dp[l] == -1) { dp[l] = 0; } // return value corresponding // to length l return dp[l]; } // Driver Code let l = 11, p = 2, q = 3, r = 5; // Calling Function let ans = findMaximum(l, p, q, r); document.write(ans); // This code is contributed by rag2127 </script> |
输出
5
复杂性分析：
- 时间复杂性： O（N）。 使用单个for循环直到长度为“N”。
- 辅助空间： O（N）。 使用数组“DP”来跟踪段
注： 这个问题也可以被认为是一个最小硬币兑换问题，因为我们得到了一个特定的长度，这个长度与需要最小硬币兑换量的值相同。现在x，y，z与给定硬币的面额相同。所以长度和数量相同，x y z和面额相同，所以我们只需要改变一个条件，而不是求最小值，我们需要求最大值，我们就能得到答案。由于最小硬币兑换问题是基本的动态规划问题，所以这也将有助于解决这个问题。
最小硬币兑换问题中需要改变的条件
for(ll i=1;i<=n;i++){ for(ll j=1;j<=3;j++) { if(i>=a[j]&&m[i-a[j]]!=-1) { dp[i]=max(dp[i],1+dp[i-a[j]]); } }}
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
