Cortar una varilla | DP-13

 

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *