@Don
int coins [] = {1, 3, 5};
int cnt [] = {7, 3, 1};
int S = 9;
Your code returns 9, for the aforementioned test case. Should not it return 3 ?
Here is my take which takes O (|number of denominators| x |S| x
|maximum count for any coin|) time and
O (|number of denominators| x |S|) time. It is quite naive dp, but I
am not too sure if there is scope of improvement.
int coins [] = {1, 3, 5};
int cnt [] = {7, 3, 1};
const int INF = 0x3f3f3f3f;
int memo [55][1005];
int
solve (int idx, int s) {
if (s == 0) return 0;
if (s < 0 || idx < 0) return INF;
if (memo [idx][s] != -1) return memo [idx][s];
int ret = INF;
for (int i = 0; i <= cnt [idx]; i++)
ret = min (ret, i + solve (idx - 1, s - coins [idx] * i)); //
Take i coins from coin [idx].
return memo [idx][s] = ret;
}
int
main () {
#ifdef LOCALHOST
freopen ("test.in", "r", stdin);
// freopen ("test.out", "w", stdout);
#endif
memset (memo, -1, sizeof (memo));
int S = 9;
int ret = solve (sizeof (coins) / sizeof (coins [0]) - 1, S);
ret = ret >= INF ? -1 : ret;
printf ("%d\n", ret);
return 0;
}
@Atul
What is the issue in recursive approach ?
On Sat, May 17, 2014 at 12:42 AM, Don <dondod...@gmail.com> wrote:
> If you find a way to do that for more than a few coins I'd be interested in
> seeing it too.
> Don
>
>
> On Thursday, May 15, 2014 3:00:04 PM UTC-4, atul007 wrote:
>>
>> @Don : i am intersted in DP bottom up approach with less time complexity.
>> solving it recursively is a simpler approach...
>>
>> On 15 May 2014 22:25, "Don" <dond...@gmail.com> wrote:
>>>
>>> How about this:
>>>
>>> const int N = 6;
>>> unsigned int coins[N] = {100,50,25,10,5,1};
>>> unsigned int count[N] = {2, 1, 1, 5, 4, 10};
>>> int best = 1000000000;
>>>
>>> int minCoins(int s, int f=0, int d=0)
>>> {
>>> if (d == 0) best = s; // It can never take more than s coins
>>> if (s < 1) return 0; // No coins required
>>> if (d >= best) return 100; // We've already used too many coins.
>>> int result=best;
>>> for(int i = f; i < N; ++i) // Don't regress
>>> {
>>> if (count[i]) // Only try coins which are available
>>> {
>>> if (coins[i] < s) // Try using this coin
>>> {
>>> --count[i];
>>> int sum = 1 + minCoins(s-coins[i], i, d+1);
>>> if (sum < result) sum = result;
>>> if ((d == 0) && (sum < best)) best = sum;
>>> ++count[i];
>>> }
>>> else if (coins[i] == s) return 1; // This coin is all we need
>>> }
>>> }
>>> return result;
>>> }
>>>
>>> int main()
>>> {
>>> int s;
>>> scanf("%d", &s);
>>> printf("The fewest coins to total to %d is %d\n", s, minCoins(s));
>>> return 0;
>>> }
>>>
>>> On Thursday, May 15, 2014 1:35:12 AM UTC-4, atul007 wrote:
>>>>
>>>> Solving coin change problem with limited coins.
>>>>
>>>> Given an array of denominations and array Count , find minimum number of
>>>> coins required to form sum S.
>>>>
>>>> for eg: coins[]={1,2,3};
>>>> count[]={1,1,3};
>>>> i.e we have 1 coin of 1$ , 1 coin of 2$ , 3 coins of 3$.
>>>>
>>>> input S = 6
>>>> output = 2
>>>>
>>>> possible combination : 3+3 = 6
>>>
>>> --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To unsubscribe from this group and stop receiving emails from it, send an
>>> email to algogeeks+...@googlegroups.com.
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to algogeeks+unsubscr...@googlegroups.com.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
