You are given a collection of coins of various denominations (different monetary

Question

You are given a collection of coins of various denominations (different monetary values) and are asked to choose some or all of the coins to pay for an item of a given price without needing to be given change - ie the exact amount. How can this be viewed as a search problem? [5 marks] You are provided with a class Coin which has a single method getValue. If the problem starts from an array of coins, how would you represent the current state? Your answer should include a class definition showing the needed fields and method signatures. You should not provide method bodies. [10 marks] Provide the Java code for a method getDaughters in your state representation that given a state, would generate the daughter states. You will not be penalised for minor syntactic errors. [10 marks]

Explanation / Answer

Suppose we want to make change for V cents. We have infinite number of coins of various denominations (different monetary values)
such that C = { C1, C2, .. , Cm} valued coins. This is a searching problem.

Examples:

Input: coins[] = {15, 10, 5, 20, 25}, V = 50
Output: Minimum 3 coins required
We can use one coin of 25 cents, one of 20 cents and one of 5 cents

Input: coins[] = {5, 8, 6, 4, 3}, V = 18
Output: Minimum 3 coins required
We can use one coin of 8 cents, one coin of 6 cents and 1 coin of 4 cents.

public class SelectionSort{
public static int[] sort(int []coins){

for(int i=0;i<coins.length-1;++i){
int index=1;
for(int j=i+1;j<coins.length;++j){
   if(coins[j]<coins[index])
index=j;
int p=coins[index];
coins[index]=coins[i];
coins[i]=p;

}
return coins;
}

public static void main(String[] args){

int coin1[] = {5, 8, 15, 20, 50, 100};
int coin2[] =sort(coin1);
for(int i:coin2){
System.out.print(i+" ");

}
}
}

abstract class Coin{
   public static void main(String[] args){
   int V;
if(V==0)
return 0;
   int coins[] = {5, 8, 15, 20, 50, 100};
   int m = coins.length;
V = 40;
//m is the size of coins array (number of different coins)
//V is the exact amount for change
abstract int getValue(int coins[], int m, int V);
}
}

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.