Tutorialspoint.dev

Maximum number of segments of lengths a, b and c

Given a positive integer N, find the maximum number of segments of lengths a, b and c that can be formed from N .

Examples :

Input : N = 7, a = 5, b, = 2, c = 5 
Output : 2 
N can be divided into 2 segments of lengths
2 and 5. For the second example,

Input : N = 17, a = 2, b = 1, c = 3 
Output : 17 
N can be divided into 17 segments of 1 or 8 
segments of 2 and 1 segment of 1. But 17 segments
of 1 is greater than 9 segments of 2 and 1.  



Approach : The approach used is Dynamic Programming. The base dp0 will be 0 as initially it has no segments. After that, iterate from 1 to n, and for each of the 3 states i.e, dpi+a, dpi+b and dpi+c, store the maximum value obtained by either using or not using the a, b or c segment.
The 3 states to deal with are :

dpi+a=max(dpi+1, dpi+a);
dpi+b=max(dpi+1, dpi+b);
dpi+c=max(dpi+1, dpi+c);

Below is the implementation of above idea :

C++

// C++ implementation to divide N into 
// maximum number of segments 
// of length a, b and c
#include <bits/stdc++.h>
using namespace std;
  
// function to find the maximum
// number of segments
int maximumSegments(int n, int a, 
                    int b, int c)
{
    // stores the maximum number of 
    // segments each index can have
    int dp[n + 1];
      
    // initialize with -1
    memset(dp, -1, sizeof(dp));
  
    // 0th index will have 0 segments
    // base case
    dp[0] = 0; 
  
    // traverse for all possible 
    // segments till n
    for (int i = 0; i < n; i++) 
    {
        if (dp[i] != -1) {
              
            // conditions
        if(i + a <= n )    //avoid buffer overflow
                dp[i + a] = max(dp[i] + 1, 
                            dp[i + a]);
                              
        if(i + b <= n ) //avoid buffer overflow
                dp[i + b] = max(dp[i] + 1, 
                            dp[i + b]);
                              
        if(i + c <= n )    //avoid buffer overflow
                dp[i + c] = max(dp[i] + 1, 
                            dp[i + c]);
        }
    }
    return dp[n];
}
  
// Driver code
int main()
{
    int n = 7, a = 5, b = 2, c = 5;
    cout << maximumSegments(n, a, b, c); 
    return 0;
}

Java

// Java implementation to divide N into
// maximum number of segments
// of length a, b and c
import java.util.*;
  
class GFG 
{
      
    // function to find the maximum
    // number of segments
    static int maximumSegments(int n, int a, 
                            int b, int c)
    {
        // stores the maximum number of
        // segments each index can have
        int dp[] = new int[n + 10];
  
        // initialize with -1
        Arrays.fill(dp, -1);
  
        // 0th index will have 0 segments
        // base case
        dp[0] = 0
  
        // traverse for all possible 
        // segments till n
        for (int i = 0; i < n; i++) 
        {
            if (dp[i] != -1
            {
  
                // conditions
                if(i + a <= n )    //avoid buffer overflow
                dp[i + a] = Math.max(dp[i] + 1
                                    dp[i + a]);
                                      
                if(i + b <= n )    //avoid buffer overflow
                dp[i + b] = Math.max(dp[i] + 1,     
                                    dp[i + b]);
                                      
                if(i + c <= n )    //avoid buffer overflow
                dp[i + c] = Math.max(dp[i] + 1
                                    dp[i + c]);
            }
        }
        return dp[n];
    }
  
    // Driver code
    public static void main(String arg[])
    {
        int n = 7, a = 5, b = 2, c = 5;
        System.out.print(maximumSegments(n, a, b, c));
    }
}
  
// This code is contributed by Anant Agarwal.

Python3

# Python implementation 
# to divide N into maximum 
# number of segments of 
# length a, b and c
  
# function to find 
# the maximum number 
# of segments
def maximumSegments(n, a, b, c) :
  
    # stores the maximum 
    # number of segments 
    # each index can have
    dp = [-1] * (n + 10)
  
    # 0th index will have 
    # 0 segments base case
    dp[0] = 0
  
    # traverse for all possible
    # segments till n
    for i in range(0, n) :
      
        if (dp[i] != -1) :
          
            # conditions
            if(i + a <= n ): # avoid buffer overflow    
                dp[i + a] = max(dp[i] + 1
                            dp[i + a])
                              
            if(i + b <= n ): # avoid buffer overflow    
                dp[i + b] = max(dp[i] + 1
                            dp[i + b])
                              
            if(i + c <= n ): # avoid buffer overflow    
                dp[i + c] = max(dp[i] + 1
                            dp[i + c])
  
    return dp[n]
  
# Driver code
n = 7
a = 5
b = 2
c = 5
print (maximumSegments(n, a, 
                    b, c))
  
# This code is contributed by 
# Manish Shaw(manishshaw1)

C#

// C# implementation to divide N into
// maximum number of segments
// of length a, b and c
using System;
  
class GFG 
{
      
    // function to find the maximum
    // number of segments
    static int maximumSegments(int n, int a, 
                            int b, int c)
    {
        // stores the maximum number of
        // segments each index can have
        int []dp = new int[n + 10];
  
        // initialize with -1
        for(int i = 0; i < n + 10; i++)
        dp[i]= -1;
          
  
        // 0th index will have 0 segments
        // base case
        dp[0] = 0; 
  
        // traverse for all possible
        // segments till n
        for (int i = 0; i < n; i++) 
        {
            if (dp[i] != -1) 
            {
  
                // conditions
                if(i + a <= n )    // avoid buffer overflow
                dp[i + a] = Math.Max(dp[i] + 1, 
                                    dp[i + a]);
                                      
                if(i + b <= n )    // avoid buffer overflow
                dp[i + b] = Math.Max(dp[i] + 1, 
                                    dp[i + b]);
                                      
                if(i + c <= n )    // avoid buffer overflow
                dp[i + c] = Math.Max(dp[i] + 1, 
                                    dp[i + c]);
            }
        }
        return dp[n];
    }
  
    // Driver code
    public static void Main()
    {
        int n = 7, a = 5, b = 2, c = 5;
        Console.Write(maximumSegments(n, a, b, c));
    }
}
  
// This code is contributed by nitin mittal

PHP

<?php
// PHP implementation to divide 
// N into maximum number of 
// segments of length a, b and c
  
// function to find the maximum
// number of segments
function maximumSegments($n, $a
                        $b, $c)
{
    // stores the maximum 
    // number of segments 
    // each index can have
    $dp = array();
  
    // initialize with -1
    for($i = 0; $i < $n + 10; $i++)
        $dp[$i]= -1;
      
  
    // 0th index will have 
    // 0 segments base case
    $dp[0] = 0; 
  
    // traverse for all possible
    // segments till n
    for ($i = 0; $i < $n; $i++) 
    {
        if ($dp[$i] != -1) 
        {
            // conditions
            if($i + $a <= $n )    // avoid buffer overflow
            $dp[$i + $a] = max($dp[$i] + 1, 
                            $dp[$i + $a]);
                              
            if($i + $b <= $n )    // avoid buffer overflow
            $dp[$i + $b] = max($dp[$i] + 1, 
                            $dp[$i + $b]);
                              
            if($i + $c <= $n )    // avoid buffer overflow
            $dp[$i + $c] = max($dp[$i] + 1, 
                            $dp[$i + $c]);
        }
    }
    return $dp[$n];
}
  
// Driver code
$n = 7; $a = 5; 
$b = 2; $c = 5;
echo (maximumSegments($n, $a
                    $b, $c));
  
// This code is contributed by 
// Manish Shaw(manishshaw1)
?>


Output :

2

Time complexity : O(n)



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter