Spoj-PIGBANK Piggy Bank Problem[Java Solution]

   Spoj Problem PIGBANK- PIGGY-BANK[Java Solution]                                          using Dynamic Programming

Problem Statement:-http://www.spoj.com/problems/PIGBANK/

With the help of Dynamic Programming concept,this problem can be easily solved.Solution of this problem using Java given below.

Java Program:-

/**
 * @(#)PIGBANK.java
 *
 *
 * @author Suyash Bhalla
 * @version 1.00 2016/3/21
 */

import java.io.*;
import java.util.*;

class PIGBANK {

public static final int INF=1000000000;


    public static void main(String args[])throws IOException{
   
    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    int T=Integer.parseInt(br.readLine());
    while(T--!=0){
    String str[]=br.readLine().split(" ");
    int E=Integer.parseInt(str[0]);
    int F=Integer.parseInt(str[1]);
   
    int N=Integer.parseInt(br.readLine());
   
    int val[]=new int[N];
    int wt[]=new int[N];
   
    int W=(F-E)+1;
    int ar[]=new int[W];
   
    for(int i=0;i<N;i++){
    str=br.readLine().split(" ");
    val[i]=Integer.parseInt(str[0]);
    wt[i]=Integer.parseInt(str[1]);
    Arrays.fill(ar,INF);
   
    }
    ar[0]=0;
   
    for(int i=1;i<=N;i++){
    for(int j=wt[i-1];j<W;j++){
    if(ar[j]>ar[j-wt[i-1]]+val[i-1]){
    ar[j]=ar[j-wt[i-1]]+val[i-1];
    }
    }
    }
   
   
    if(ar[W-1]==INF){
    System.out.println("This is impossible.");
    }else{
    System.out.println("The minimum amount of money in the piggy-bank is "+ar[W-1]+".");
    }
   
   
   
   
   
    }
   
    }
 
 
 
}

Input:-

3
10 110
2
1 1
30 50
10 110
2
1 1
50 30
1 6
2
10 3
20 4

Output:-

The minimum amount of money in the piggy-bank is 60.
The minimum amount of money in the piggy-bank is 100.
This is impossible.

--------------X--------------X--------------X--------------X--------------X--------------X--------------X---------