Dada una barra de n pulgadas de longitud y una array de precios que incluye los precios de todas las piezas de tamaño menor que n. Determine el valor máximo que se puede obtener cortando la varilla y vendiendo las piezas. Por ejemplo, si la longitud de la varilla es 8 y los valores de las diferentes piezas se dan a continuación, entonces el valor máximo que se puede obtener es 22 (cortando en dos piezas de longitudes 2 y 6)
length | 1 2 3 4 5 6 7 8 -------------------------------------------- price | 1 5 8 9 10 17 17 20
Y si los precios son los siguientes, entonces el valor máximo que se puede obtener es 24 (cortando en ocho piezas de longitud 1)
C++
// A recursive solution for Rod cutting problem #include <bits/stdc++.h> #include <iostream> #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 index, int n) { // base case if (index == 0) { return n * price[0]; } //At any index we have 2 options either //cut the rod of this length or not cut //it int notCut = cutRod(price,index - 1,n); int cut = INT_MIN; int rod_length = index + 1; if (rod_length <= n) cut = price[index] + cutRod(price,index,n - rod_length); return max(notCut, cut); } /* 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 - 1, size); getchar(); return 0; } //This code is contributed by Sanskar
Java
// Java recursive solution for Rod cutting problem 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 index, int n) { // base case if (index == 0) { return n * price[0]; } // At any index we have 2 options either // cut the rod of this length or not cut // it int notCut = cutRod(price, index - 1, n); int cut = Integer.MIN_VALUE; int rod_length = index + 1; if (rod_length <= n) cut = price[index] + cutRod(price, index, n - rod_length); return Math.max(notCut, cut); } /* Driver program to test above functions */ public static void main(String args[]) { int arr[] = { 1, 5, 8, 9, 10, 17, 17, 20 }; int size = arr.length; System.out.println("Maximum Obtainable Value is " + cutRod(arr, size - 1, size)); } } // This code is contributed by Lovely Jain
C++
// A memoization solution for Rod cutting problem #include <bits/stdc++.h> #include <iostream> #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 index, int n, vector<vector<int> >& dp) { // base case if (index == 0) { return n * price[0]; } if (dp[index][n] != -1) return dp[index][n]; // At any index we have 2 options either // cut the rod of this length or not cut // it int notCut = cutRod(price, index - 1, n,dp); int cut = INT_MIN; int rod_length = index + 1; if (rod_length <= n) cut = price[index] + cutRod(price, index, n - rod_length,dp); return dp[index][n]=max(notCut, cut); } /* 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]); vector<vector<int> > dp(size, vector<int>(size + 1, -1)); cout << "Maximum Obtainable Value is " << cutRod(arr, size - 1, size, dp); getchar(); return 0; } // This code is contributed by Sanskar
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 */
Python3
# 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>
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_length 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_length 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 \n", 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_length 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_length 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_length 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_length 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>
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA