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