this sum is taken from geeksforgeeks

if you want to solve you can go to this link

Given an integer N denoting the Length of a line segment. you need to cut the line segment in such a way that the cut length of a line segment each time is integer either x , y or z. and after performing all cutting operation the total number of cutted segments must be maximum.

N=4
x,y,z=2 1 1

In first test case, total length is 4, and cut lengths are 2, 1 and 1.  We can make maximum 4 segments each of length 1.
so output=>4

N=5
x=5 ,y=3,z=2
we can make two segments of lengths 3 and 2.
output=>2

lets use dynamic programming to solve this question:
c++ implementation:

t is the no.of test cases:

```#include <iostream>
#include <bits/stdc++.h>
using namespace std;

void mtcs(int a[],int length)
{
int dp[3][length+1];
int j=0;
for(int i=0;i<3;i++)
{
for(j=0;j<=length;j++)
{  if(j==0)
dp[i][j]=0;

else if(i==0)
{   if(j%a[i]==0)
dp[i][j]=j/a[i];
else
dp[i][j]=0;
}

else{
if(a[i]>j)
dp[i][j]=dp[i-1][j];

else
{
if(dp[i-1][j]==0 && dp[i][j-a[i]]==0 && j-a[i]!=0)
dp[i][j]=0;

else
dp[i][j]=max(dp[i-1][j],dp[i][j-a[i]]+1);
}

}

}
}

cout<<dp[2][j-1];
}

int main() {
int t; cin>>t;
while(t--)
{  int length;   cin>>length;

int a[3];
cin>>a[0]>>a[1]>>a[2];
sort(a,a+3);

mtcs(a,length);
cout<<endl;
}
return 0;
}

```
darkmode