HW2D - Editorial

editorial
, ,
1

PROBLEM LINK:
Practice
Source

Author: SQU_Test

DIFFICULTY:
Medium

PREREQUISITES:
Dynamic Programming

PROBLEM:
Mohammed has a wire, its length is n. He wants to cut the wire in a way that fulfils the following two conditions:
• After the cutting each wire piece should have length a, b or c.
• After the cutting the number of wire pieces should be maximum.

Help Mohammed and find the number of wire pieces after the required cutting.

EXPLANATION:
The problem is to maximize x + y + z subject to ax + by + cz = n. Constraints are low, so simply iterate over two variables (say x and y) and find the third variable (if any) from the second equation. Find the maximum over all feasible solutions.

Other approaches: Use dynamic programming with each state being the remainder of wire. Select the next piece to be a, b or c.

TIME COMPLEXITY:
Time complexity of the solution is O(n) using dynamic programming.

SOLUTIONS:

Setter’s Solution 
  #include <iostream>
  #include<vector>
  #include<algorithm>
  using namespace std;
   
  int main()
  {
      int n,a,b,c,x,y,z;
      cin>>n>>a>>b>>c;

      vector<int> dp(n+1);

      dp[0]=0;

      for(int i=1;i<=n;i++)
      {
          x=y=z=-1;

          if(i>=a)
              x=dp[i-a];

          if(i>=b)
              y=dp[i-b];

          if(i>=c)
              z=dp[i-c];

          if(x==-1 && y==-1 && z==-1)
              dp[i]=-1;

          else
              dp[i]=max(max(x,y),z)+1;
      }


      cout<<dp[n]<<endl;
      return 0;
  }
2

i tried by top down apporach but its wrong

using namespace std;
int dp[4500];
int ans(int n,int d,int e,int f)
{
    if(n==0)
    {
        return dp[n]=1;
    }
    if(n<0)
    {
        return dp[n]=0;
    }
    if(dp[n]!=-1)
    {
        return dp[n];
    }
    return dp[n]=max(1+ans(n-f,d,e,f),max(1+ans(n-d,d,e,f),1+ans(n-e,d,e,f)));
    
}
int main()
{
 int n,a,b,c;
 memset(dp,-1,4500);
 cin>>n>>a>>b>>c;
 cout<<ans(n,a,b,c)<<endl;
    return 0;
}```