Maximum Coin Spend Problem using Dynamic Programming in Java

In this Java tutorial, We are going to discuss Maximum coin Problem using DP. In the problem, we are provided with two input arrays of n values in which one array consists of distances of different cities from the origin and another array consist of corresponding coins needed to travel that city.

Solve maximum coin spend problem in Java

So, we are provided with a maximum distance which we can travel. So, we have to spend the maximum coin in traveling cities in almost maximum distance.

What is Dynamic Programming?

Dynamic Programming is an Optimisation over recursion. In some problem, we have to compute the same input again and again for some values there we can use DP to avoid this thing. We simply store the results of subproblems, so that we do not re-compute them if needed later. This also reduces the time complexity from exponential to polynomial.

Step by Step Approach to solve maximum coin spend problem in Java

1.  First, we have input a value n and two n size arrays. First array d[] consists of different cities from origin and second array c[] consists of corresponding coins spend in traveling i-th city. We have taken a maximum value ‘ max ‘ .
2. In function result we passed  4 parameters max , c[] , d[]   and n . In that function, we use dynamic programming approach in bottom-up manner .
3. For a i-th city at a distance d[i] we have two choices either to include that city or not. If the distance of ith city is greater than maximum distance ‘d’ then we cannot include that city.
4. For including a city still, we have to check for a maximum value that we can get from including that city or excluding that city if that city is included we decrease its weight from ‘max’ otherwise continue with the previous values stored.
5. In filling up the two-dimension Dp array at last we have the maximum value which will be our answer.

You may also learn,

• FizzBuzz Problem In Java- A java code to solve FizzBuzz problem
• Guess The Number Game Using Java with Source Code
• How to find Maximum Pairwise Product in Java using Naive approach

Code to print maximum coin spend in Java

import java.util.Scanner;
  
 class Codespeedy
      
    {
               
               static int result(int max , int d[] , int c[] , int n)
            
            {
                      int i,j;
                        
                               int Dp[][] = new int [n+1][max+1];
         
                           for(i=0;i<=n;i++)
                         {
                                for(j=0;j<=max;j++)
                              {
                                  
                                    if(i==0 || j==0)
                                     Dp[i][j]=0;
                          
                                   else if (d[i-1]<=j)
                                     Dp[i][j]=(c[i-1]+Dp[i-1][j-d[i-1]])>(Dp[i-1][j]) ? (c[i-1]+Dp[i-1][j-d[i-1]]):( Dp[i-1][j]) ;
                          
                                    else
                                      Dp[i][j]=Dp[i-1][j];
                               }
                         }
              
              return Dp[n][max];
       }
     
     public static void main ( String args[])
      {
         
        Scanner scan = new Scanner(System.in);
            
          int n=scan.nextInt();
            
          int c[] = new int [n+1];
          int d[] = new int [n+1];
          
          for(int i=0;i<n;i++)
             d[i]=scan.nextInt();
            
          for(int i=0;i<n;i++)
             c[i]=scan.nextInt();
            
            int max = scan.nextInt();
            
            System.out.println(result(max,d,c,n));
              
      }
}

        INPUT

4
20 30 40 10
100 120 500 750
50

OUTPUT

1250

So, In the example case, we have given a value of ‘n’ as 4. And input two n size array onr representing the distance of ith city from the origin and another coins spend in traveling that ith city. We have taken the maximum value of the distance to be travel as 50.
So, the maximum coins that we can spend are on traveling 3th and 4th city. Total coins spend in traveling that cities 1250 coins and total distance for traveling that cities are 50 which is less than or equal to max.

Java solution to maximize the chances of winning in Monty-Hall Paradox Problem