@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 <[email protected]> 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" <[email protected]> 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 [email protected].
>
> --
> 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 [email protected].
--
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 [email protected].
