You are given an array of gold coins of denominations of the powers of 2. And, you are supposed to fill them in a knapsack of a given capacity.
Every gold coin can be split into 2 gold coins of equal denomination. You are supposed to return the minimum number of splits required to fill the knapsack completely. Return a -1 if it's not possible.
Ex:- A = [1,32,1] B = 10
split 32 into 16 each. Split 16 into 8 each. Now, use an 8 and the two 1s that are already in the array to get to the answer. You return a 2 here.
Now, i can think of a dynamic programming solution where i try all possible combinations. Like, split a big coin until you're able to put it into the knapsack and another case where you completely skip that entry (For example, skip 32 entirely or make 32 into 8 and move on).
import java.util.*;
class Solution
{
int recur(int[] a, int i, int b,int[][] dp)
{
if(b==0)
return 0;
if(i>a.length-1)
return -1;
if(dp[i][b]!=-1)
return dp[i][b];
int p,q;
if(b>=a[i])
p = recur(a,i+1,b-a[i],dp);
else
{
int temp=a[i],count=0;
while(b<temp)
{
temp=temp/2;
count++;
}
p = recur(a,i+1,b-temp,dp);
if(p!=-1)
p+=count;
}
q = recur(a,i+1,b,dp);
if(p==-1 && q==-1)
return dp[i][b]=-1;
else if(p!=-1 && q!=-1)
return dp[i][b]=Math.min(p,q);
else
return dp[i][b]=Math.max(p,q);
}
int goldcoin(int[] a, int b)
{
int[][] dp = new int[a.length+1][b+1];
for (int[] row : dp)
Arrays.fill(row, -1);
return recur(a,0,b,dp);
}
}
public class Main
{
public static void main(String[] args)
{
int[] a = {32,64,64,4,8,1,1,128,1024};
int b=51;
System.out.print(new Solution().goldcoin(a,b));
}
}But, i'm struggling with keep a track of the other coins produced when i split. If the question just says you can split and only use one of the coins, problem solved. But, i need to keep a track of the other coin produced. Firstly, can this even be solved via Dynamic programming? If yes, please tell me how i can modify my code
