Maximize The Cut Segments

Question

**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. **

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

int findMaxSegments(int a[],int target,int n,int count)
{
    if(n == 0 && target > 0)
    return 0;

    if(target == 0)    
    return count;

    if(a[n-1] <= target)
    return max(findMaxSegments(a,target-a[n-1],n,count+1),findMaxSegments(a,target,n-1,count));

    else
    return findMaxSegments(a,target,n-1,count);
}

int main()
 {
    //code
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int queries;
    cin>>queries;
    while(queries--)
    {
        int sum;
        cin>>sum;
        int arr[3];
        
        for(int i=0;i<3;i++)
        cin>>arr[i];
        
        int count = findMaxSegments(arr,sum,3,0);
        
        cout<<count<<"\n";
    }
    return 0;
}

above is recursive solution which is working perfect but taking more time,can anyone help me to change this above code to memoization or top-down dp?

you can check the code for this

INPUT-  query->1
N->2683
x,y,z->83 26 2709

OUTPUT 101

Please read the answers to [Why should I not #include ?](https://stackoverflow.com/q/31816095/5910058) as well as [Why is "using namespace std;" considered bad practice?](https://stackoverflow.com/q/1452721/5910058) — Jesper Juhl, Aug 22 '20 at 13:08
You are optimizing `max(a + b + c)` with `a*x + b*y + c*z = N`, `a >= 0`, `b >= 0`, `c >= 0` and `a, b, c in IN`. I think it's a mathematical problem and not a programming problem: https://en.wikipedia.org/wiki/Integer_programming (Okay, in English it's called integer programming) — Thomas Sablik, Aug 22 '20 at 13:20

score 1 · Answer 1 · answered Aug 22 '20 at 15:49

Let's say we arrange the numbers so that x < y < z.

Ideally, we would like to maximize the number of segments by cutting into lengths of x to give N/x segments. This usually isn't possible, because N isn't divisible by x, so we will have to use some y and z.

Every time we use a different length, we can calculate how much it costs us in segments compared to the ideal. Using a y costs y/x - y/y = y/x - 1 = (y-x)/x segments, and using a z costs (z-x)/x segments.

One way to solve your problem is to find the smallest cost combination of y and z segments such that the remaining length is divisible by x. We can use Dijkstra's algorithm over the implicit graph to do this. Each possible remaining length is a vertex, and the edges represent using a y or z to get to the next length.

Basically this just boils down to using a priority queue to evaluate the combinations of y and z counts in order of cost, until we get to a remainder divisible by x.

Maximize The Cut Segments

1 Answers1