Рубрики

Максимальное сокращение продукта | DP-36

Учитывая длину веревки n метров, разрежьте веревку на различные части целочисленной длины таким образом, чтобы максимально увеличить произведение длин всех частей. Вы должны сделать хотя бы один разрез. Предположим, что длина каната составляет более 2 метров.

Примеры:

Input: n = 2
Output: 1 (Maximum obtainable product is 1*1)

Input: n = 3
Output: 2 (Maximum obtainable product is 1*2)

Input: n = 4
Output: 4 (Maximum obtainable product is 2*2)

Input: n = 5
Output: 6 (Maximum obtainable product is 2*3)

Input: n = 10
Output: 36 (Maximum obtainable product is 3*3*4)

1) Оптимальная подструктура:
Эта проблема похожа на проблему резки стержня. Мы можем получить максимальный продукт, сделав разрез в разных положениях и сравнив значения, полученные после разреза. Мы можем рекурсивно вызвать ту же функцию для части, полученной после разреза.

Пусть maxProd (n) будет максимальным произведением для веревки длины n. maxProd (n) можно записать следующим образом.

maxProd (n) = max (i * (ni), maxProdRec (ni) * i) для всех i в {1, 2, 3 .. n}

2) Перекрывающиеся подзадачи
Ниже приводится простая рекурсивная реализация проблемы. Реализация просто следует рекурсивной структуре, упомянутой выше.

C ++

// Наивный рекурсивный метод поиска продукта максимума
#include <iostream>

using namespace std;

  
// Сервисная функция для получения максимум двух и трех целых

int max(int a, int b) { return (a > b)? a : b;}

int max(int a, int b, int c) { return max(a, max(b, c));}

  
// Основная функция, которая возвращает максимально возможный продукт
// из веревки длиной n

int maxProd(int n)

{

    // Базовые случаи

    if (n == 0 || n == 1) return 0;

  

    // Делаем разрез в разных местах и берем максимум всех

    int max_val = 0;

    for (int i = 1; i < n; i++)

      max_val = max(max_val, i*(n-i), maxProd(n-i)*i);

  

    // Возвращаем максимум всех значений

    return max_val;

}

  
/ * Программа драйвера для проверки вышеуказанных функций * /

int main()

{

    cout << "Maximum Product is " << maxProd(10);

    return 0;

}

Джава

// Java программа для поиска продукта maxium

import java.io.*;

  

class GFG {

  

    // Основная функция, которая возвращает

    // максимальный продукт, который можно получить из

    // веревка длиной n

    static int maxProd(int n)

    {

        // Базовые случаи

        if (n == 0 || n == 1) return 0;

  

        // Делаем разрез в разных местах

        // и берем максимум из всех

        int max_val = 0;

        for (int i = 1; i < n; i++)

        max_val = Math.max(max_val,

                  Math.max(i * (n - i),

                   maxProd(n - i) * i));

  

        // Возвращаем максимум всех значений

        return max_val;

    }   

  

    / * Программа драйвера для проверки вышеуказанных функций * /

    public static void main(String[] args)

    {

        System.out.println("Maximum Product is " 

                            + maxProd(10));

    }

}
// Этот код предоставлен Prerna Saini

python3

# Основная функция, которая возвращает максимум
# продукт, получаемый из веревки длины n

  

def maxProd(n):

      

    # Базовые случаи

    if (n == 0 or n == 1):

        return 0

   

    # Сделать разрез в разных местах

    # и взять максимум из всех

    max_val = 0

    for i in range(1, n - 1):

        max_val = max(max_val, max(i * (n - i), maxProd(n - i) * i))

   

    # Возвращаем максимум всех значений

    return max_val;

  

   
# Драйверная программа для проверки вышеуказанных функций

print("Maximum Product is ", maxProd(10));

      
# Это участие
# Сумит Судхакар

C #

// C # программа для поиска продукта maxium

using System;

  

class GFG {

      

    // Основная функция, которая возвращает

    // максимально возможный продукт

    static int maxProd(int n)

    {

  

        // n равно 2 или 3

        // быть обработанным явно

        if (n == 2 || n == 3)

            return (n - 1);

  

        // Продолжаем удалять части размера

        // 3, а n больше 4

        int res = 1;

        while (n > 4) {

            n -= 3;

  

            // Продолжаем умножать 3 на res

            res *= 3;

        }

  

        // умноженная последняя часть

        // по предыдущим частям

        return (n * res);

    }

  

    // Код драйвера

    public static void Main()

    {

        Console.WriteLine("Maximum Product is "

                                + maxProd(10));

    }

}

  
// Этот код предоставлен Sam007

PHP

<?php
// Наивный рекурсивный метод для
// найти продукт maxium

  
// Сервисная функция для получения
// максимум два и три целых числа

function max_1($a, $b, $c

    return max($a, max($b, $c));

  
// Основная функция, которая возвращает
// максимально возможный продукт
// из веревки длиной n

function maxProd($n

    // Базовые случаи

    if ($n == 0 || $n == 1) return 0; 

  

    // Делаем разрез в разных местах

    // и берем максимум из всех

    $max_val = 0; 

    for ($i = 1; $i < $n; $i++) 

    $max_val = max_1($max_val, $i * ($n - $i), 

               maxProd($n - $i) * $i); 

  

    // Возвращаем максимум всех значений

    return $max_val

  
// Код драйвера

echo "Maximum Product is " . maxProd(10); 

  
// Этот код добавлен
// ChitraNayal
?>


Выход:

Maximum Product is 36

Учитывая вышеописанную реализацию, ниже приведено дерево рекурсии для веревки длиной 5.

В приведенном выше дереве частичной рекурсии mP (3) решается дважды. Мы видим, что есть много подзадач, которые решаются снова и снова. Поскольку те же самые подзадачи вызываются снова, эта проблема имеет свойство Перекрывающиеся подзадачи. Таким образом, проблема имеет оба свойства (см. Это и это ) задачи динамического программирования. Как и другие типичные проблемы динамического программирования (DP) , повторных вычислений с одинаковыми подзадачами можно избежать, построив временный массив val [] снизу вверх.

// Решение для динамического программирования для Max Product Problem

int maxProd(int n)

{

   int val[n+1];

   val[0] = val[1] = 0;

   

   // Строим таблицу val [] снизу вверх и возвращаем

   // последняя запись из таблицы

   for (int i = 1; i <= n; i++)

   {

      int max_val = 0;

      for (int j = 1; j <= i/2; j++)

         max_val = max(max_val, (i-j)*j, j*val[i-j]);

      val[i] = max_val;

   }

   return val[n];

}

Сложность по времени решения динамического программирования составляет O (n ^ 2) и требует O (n) дополнительного пространства.

Хитрое решение:
Если мы увидим некоторые примеры этой проблемы, мы можем легко наблюдать следующую картину.
Максимальный продукт может быть получен путем многократной резки деталей размером 3, в то время как размер больше 4, с сохранением последней части размером 2, 3 или 4. Например, n = 10, максимальный продукт получается 3, 3, 4. Для n = 11 максимальный продукт получается 3, 3, 3, 2. Далее следует реализация этого подхода.

C ++

#include <iostream>

using namespace std;

  
/ * Основная функция, которая превращает максимально возможный продукт * /

int maxProd(int n)

{

   // n равно 2 или 3 должно быть обработано явно

   if (n == 2 || n == 3) return (n-1);

  

   // Продолжаем удалять части размером 3, пока n больше 4

   int res = 1;

   while (n > 4)

   {

       n -= 3;

       res *= 3; // Продолжаем умножать 3 на res

   }

   return (n * res); // Последняя часть, умноженная на предыдущие части

}

  
/ * Программа драйвера для проверки вышеуказанных функций * /

int main()

{

    cout << "Maximum Product is " << maxProd(10);

    return 0;

}

Джава

// Java программа для поиска максимального продукта

import java.io.*;

  

class GFG {

  

    / * Основная функция, которая возвращает

    максимально возможный продукт * /

    static int maxProd(int n)

    {

      

    // n равно 2 или 3 должны быть обработаны

    // явно

    if (n == 2 || n == 3) return (n-1);

  

    // Продолжаем удалять части размером 3

    // пока n больше 4

    int res = 1;

    while (n > 4)

    {

        n -= 3;

          

        // Продолжаем умножать 3 на res

        res *= 3

    }

      

    // Последняя часть, умноженная на

    // предыдущие части

    return (n * res); 

    }

  

    / * Программа драйвера для проверки вышеуказанных функций * /

    public static void main(String[] args)

    {

        System.out.println("Maximum Product is "

                            + maxProd(10));

    }   

}
// Этот код предоставлен Prerna Saini

python3

# Основная функция, которая возвращает
# максимально возможный продукт

  

def maxProd(n):

      

    # n равно 2 или 3

    # обрабатываться явно

    if (n == 2 or n == 3):

        return (n - 1)

   

    # Продолжайте удалять части размером 3

    # в то время как n больше 4

    res = 1

    while (n > 4):

        n -= 3;

           

        # Продолжайте умножать 3 на Res

        res *= 3

      

    # Последняя часть умножена

    # по предыдущим частям

    return (n * res)

  
# Драйверная программа для проверки вышеуказанных функций

print("Maximum Product is ", maxProd(10));

      
# Этот код добавлен
# Сумит Судхакар

C #

// C # программа для поиска продукта maxium

using System;

  

class GFG {

  

    // Основная функция, которая возвращает

    // максимальный продукт, который можно получить из

    // веревка длиной n

    static int maxProd(int n)

    {

        // Базовые случаи

        if (n == 0 || n == 1)

            return 0;

  

        // Делаем разрез в разных местах

        // и берем максимум из всех

        int max_val = 0;

        for (int i = 1; i < n; i++)

            max_val = Math.Max(max_val,

                    Math.Max(i * (n - i),

                     maxProd(n - i) * i));

  

        // Возвращаем максимум всех значений

        return max_val;

    }

  

    // Код драйвера

    public static void Main()

     {

        Console.WriteLine("Maximum Product is "

                                + maxProd(10));

     }

}

  
// Этот код предоставлен Sam007

PHP

<?php

  
/ * Основная функция, которая возвращает

   максимально возможный продукт * /

function maxProd($n)

{

      
// n равно 2 или 3
// быть обработанным явно

if ($n == 2 || $n == 3) 

    return ($n - 1);

  
// Продолжаем удалять части размера
// 3, а n больше 4

$res = 1;

while ($n > 4)

{

    $n = $n - 3;

      

    // Продолжаем умножать 3 на res

    $res = $res * 3; 

}

  
// умноженная последняя часть
// по предыдущим частям

return ($n * $res); 

}

  
// Код драйвера

echo ("Maximum Product is ");

echo(maxProd(10));

  
// Этот код добавлен
// от Shivi_Aggarwal
?>


Выход:

Maximum Product is 36

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Максимальное сокращение продукта | DP-36

0.00 (0%) 0 votes