Data Structure and Algorithsm : Problem Name: Paying Up (Solution in Java)

/*

* Author: Bishnu Patro

Problem Name: Paying Up

Problem Statement: In the following code, we are solving the paying up problem.

The paying up problem say, suppose you have some currency notes (say: numberOfNotes) and

were asked to pay to the robber the amount (say: robbersSum) asked by him and you have the number of notes

in different denominations in an array(say listofNotes), then how you can check do you have the required robbersSum

demanded from given set of currency notes. The method will return true, if you have required currency notes in proper

denomination to pay the robbers sum otherwise it will return false.

//For understanding the algorithm

//http://www.codechef.com/wiki/tutorial-paying

*/

package Test;

public class PayingUp {

public static void main(String[] args) {

//Example 1

int numberOfNotes = 3;

int robbersSum = 3;

int[] listofNotes = new int[]{1,1,1};

System.out.println("Results of example1 : " + payingUp(numberOfNotes,robbersSum,listofNotes));

//Example 2

int numberOfNotes1 = 5;

int robbersSum1 = 11;

int[] listofNotes1 = new int[]{1,2,4,8,16};

System.out.println("Results of example2 : " + payingUp(numberOfNotes1,robbersSum1,listofNotes1));

//Example 3

int numberOfNotes2 = 5;

int robbersSum2 = 19;

int[] listofNotes2 = new int[]{1,7,4,10,16};

System.out.println("Results of example3 : " + payingUp(numberOfNotes2,robbersSum2,listofNotes2));

}

public static boolean payingUp(int numberOfNotes,int robbersSum,int[] listofNotes)

{

System.out.println("Number of Subsets: " + Math.pow(2, numberOfNotes));

for(int i = 1; i < Math.pow(2, numberOfNotes); i++)

{

int sum = 0;

for(int j = 0; j < numberOfNotes; j++)

{

//For understanding bitwise left shift operator

//http://stackoverflow.com/questions/10910913/how-do-shift-operators-work-in-java

//(1<<j) means shift (1 binary (01) by value of j)

System.out.println("j value in binary: " + Integer.toBinaryString(j) + " Left Shift Operator: "+ (1<<j) + " valueOfOperation in binary: " + Integer.toBinaryString(1<<j));

System.out.println("i value in binary: " + Integer.toBinaryString(i) + " bit operation: " + (i & (1<<j)) + " bit operation value in binary: " + Integer.toBinaryString((i & (1<<j))));

if((i & (1<<j)) != 0)

sum = sum + listofNotes[j];

}

System.out.println("subset count in iteration:" + i);

if(sum == robbersSum)

return true;

}

return false;

}

}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s