/
coins.java
56 lines (46 loc) · 1.5 KB
/
coins.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
import java.io.*;
class coins
{
// m is size of coins array
// (number of different coins)
static int minCoins(int coins[], int m, int V)
{
// table[i] will be storing
// the minimum number of coins
// required for i value. So
// table[V] will have result
int table[] = new int[V + 1];
// Base case (If given value V is 0)
table[0] = 0;
// Initialize all table values as Infinite
for (int i = 1; i <= V; i++)
table[i] = Integer.MAX_VALUE;
// Compute minimum coins required for all
// values from 1 to V
for (int i = 1; i <= V; i++) {
// Go through all coins smaller than i
for (int j = 0; j < m; j++){
if (coins[j] <= i) {
int sub_res = table[i - coins[j]];
if (sub_res != Integer.MAX_VALUE
&& sub_res + 1 < table[i]) {
table[i] = sub_res + 1;
System.out.println(sub_res);
}
}
}
}
if(table[V]==Integer.MAX_VALUE)
return -1;
return table[V];
}
// Driver program
public static void main (String[] args)
{
int coins[] = {1, 5, 3, 6};
int m = coins.length;
int V = 8;
System.out.println ( "Minimum coins required is "
+ minCoins(coins, m, V));
}
}