Spoj-PARTY - Party Schedule Java Solution

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

Explanation:

This problem can be easily sovled by Dynamic Programming Approach.This problem can be solved  by two methods i.e. recursive approach and iterative approach.Here, an iterative approach is given.The key point to solve problem is that which party is to be selected or not and to maximize the fun and cost should be in budget.

The first example case data maintained is given i.e.

5 3

1 60

2 100

3 120

Data maintained for this case:

     0     1     2      3      4       5

0   0     0     0      0      0       0

1   0    60    60    60    60     60

2   0    60    100  160  160   160

3   0    60    100  120  180   220

Program:

/**

 * @(#)PARTY.java

 *

 *

 * @author Suyash Bhalla

 * @version 1.00 2015/12/20

 */

import java.io.*;

class PARTY {

    public static void main(String args[])throws IOException{

   

    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

   

    while(true){

   

    String temp[]=br.readLine().split(" ");

   

    int budget=Integer.parseInt(temp[0]);

    int n=Integer.parseInt(temp[1]);

   

    if(budget==0&&n==0){

    break;

    }

   

    int ar[][]=new int[n+1][budget+1];

   

    int cost[]=new int[n];

    int val[]=new int[n];

   

    for(int i=0;i<n;i++){

    temp=br.readLine().split(" ");

    cost[i]=Integer.parseInt(temp[0]);

    val[i]=Integer.parseInt(temp[1]);

    }

   

    for(int i=0;i<n+1;i++){

    for(int b=0;b<budget+1;b++){

   

    if(i==0||b==0){

    ar[i][b]=0;

    }else if(cost[i-1]<=b){

    ar[i][b]=Math.max(val[i-1]+ar[i-1][b-cost[i-1]],ar[i-1][b]);

    }else{

    ar[i][b]=ar[i-1][b];

    }

   

    }

    }

    int i=n,b=budget;

    while(ar[i][b]==ar[i][b-1]){

    b--;

    }

   

   

    System.out.println(b+" "+ar[n][budget]);//find(budget,cost,val,n-1));

   

   

    br.readLine();

    }

   

    }

    

}

Sample Input:

5 3

1 60

2 100

3 120

50 10

12 3

15 8

16 9

16 6

10 2

21 9

18 4

12 4

17 8

18 9 

50 10

13 8

19 10

16 8

12 9

10 2

12 8

13 5

15 5

11 7

16 2

0 0

Sample Output:

5 220

49 26

48 32

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