Reputation: 2154
I was trying to do this problem, where given coins of certain denomination, I want to find the maximum number of coins to make change.
Example Say, I'm given coins of value 3 and 5, and I want to make change for 15, the solution would be {3,3,3,3,3} (Thanks JoSSte for pointing out) Similarly, say, given coins of value 3 and 5, and I want to make change for 7,I need to display "No solution possible"
I was able to do this for Finding Minimum number of coins as follows
import java.util.ArrayList;
import java.util.Arrays;
public class Minimum
{
static int[] options = {5,3};
public static void main(String[] args)
{
ArrayList<Integer> result = new ArrayList<Integer>();
result = fun(15);
if(result.size() == 999)
System.out.println("Not possible to make change with this denomination");
else
{
for(int i = 0;i<result.size();i++)
System.out.print(result.get(i));
}
}
static ArrayList<Integer> fun(int n)
{
if(n == 0)
{
ArrayList<Integer> totalret = new ArrayList<Integer>();
return totalret;
}
if(n < 0)
{
ArrayList<Integer> totalret = new ArrayList<Integer>(Arrays.asList(new Integer[999]));
return totalret;
}
ArrayList<Integer> totalret = new ArrayList<Integer>(Arrays.asList(new Integer[999]));
for(int i = 0;i<options.length;i++)
{
ArrayList<Integer> reci = fun(n-options[i]);
ArrayList<Integer> reti = new ArrayList<Integer>();
reti.addAll(reci);
reti.add(options[i]);
if(reti.size() < totalret.size())
totalret = reti;
}
return totalret;
}
}
Notice that I have a check called if(n<0) where combinations that do not add up to the sum are removed from the options by setting their size to a very large number that cannot be the minimum.
However, how can I modify the above to find the maximum number of coins
Upvotes: 0
Views: 4562
Reputation: 1
Here is coin change dp code in c++.
int coin[] = {3, 5}; //initialize array
int make;
int dp[2][100];
int call(int i, int amount)
{
if(i >= 2) { // All coins have been taken
if(amount == make) return 1;
return 0;
}
if(dp[i][amount] != -1) return dp[i][amount];
int ret1 = 0, ret2 = 0;
// try to take coin i
if(amount + coin[i] <= make) ret1 = call(i, amount + coin[i]);
ret2 = call(i+1, amount); // don't take coin i
return dp[i][amount] = ret1 | ret2; // is possible or not?
}
int main()
{
make = 7;
memset(dp, -1, sizeof(dp));
if(call(0, 0) == 0) cout << "not possible" << endl;
else cout << "possible" << endl;
return 0;
}
Upvotes: 0
Reputation: 147
For your solution the you have to check the condition for n=1,2. if n=1,2 you can return ans as 999.
Your function must be as follow
static ArrayList<Integer> fun(int n)
{
if(n == 0)
{
ArrayList<Integer> totalret = new ArrayList<Integer>();
return totalret;
}
if(n < 0 || n==1 || n==2)
{
ArrayList<Integer> totalret = new ArrayList<Integer>(Arrays.asList(new Integer[999]));
return totalret;
}
ArrayList<Integer> totalret = new ArrayList<Integer>(Arrays.asList(new Integer[999]));
for(int i = 0;i<options.length;i++)
{
ArrayList<Integer> reci = fun(n-options[i]);
ArrayList<Integer> reti = new ArrayList<Integer>();
reti.addAll(reci);
reti.add(options[i]);
if(reti.size() < totalret.size())
totalret = reti;
}
return totalret;
}
Hope this should work..
Upvotes: 1