fork(1) download
copy 
  1. //
  2. //  coin.c
  3. //  coinDP
  4. //
  5. //  Created by vaibhav gautam on 11/28/14.
  6. //  Copyright (c) 2014 vaibhav gautam. All rights reserved.
  7. //
  8. //  Given a list of N coins, their values (V1, V2, ... , VN),
  9. //  and the total sum S. Find the minimum number of coins the sum of which is
  10. //  S (we can use as many coins of one type as we want), or report that it's
  11. //  not possible to select coins in such a way that they sum up to S.
  12.  
  13.  
  14. #include <stdio.h>
  15. #include <stdint.h>
  16.  
  17. int mincount(int change[], int changeSize, int SUM)
  18. {
  19.     int table[SUM + 1];
  20.  
  21.     table[0] = 0;
  22.     int min = INT32_MAX;
  23.     int sum = 0;
  24.     int i = 0;
  25.     int j = 0;
  26.  
  27.     for (sum = 1; sum <= SUM; sum++) {
  28.         for (j = 0; j < changeSize; j++) {
  29.             // Pick first coin and substract with the sum
  30.             // Check if sum is less than 0
  31.             if (sum - change[j] < 0) {
  32.                 continue;
  33.             } else if (sum - change[j] == 0) {
  34.                 // This is the case when sum is either 1, 5, 10, 25
  35.                 // In this case mininum number of coin required is 1
  36.                 min = 1;
  37.                 break;
  38.             }
  39.  
  40.             // This is case when we say sum is 3
  41.             // In this case lets start with first coint which is 1
  42.             // If we choose coint 1 then the sum left os 3 - 1 = 2
  43.             // Given we are calculating for sum 3 means we have already
  44.             // calculated for sum 2. So go to table for sum = 2 and
  45.             // get the min number of ways sum 2 is computed.
  46.             // Here i is the sum i.e. lets say as per our example
  47.             // i = 3, j = 0
  48.             // 1 + table[3 - change[0]];
  49.             // 1 + table[3 - 1];
  50.             // 1 + table[2];
  51.             // 1 + 2 = 3
  52.             // Sum 3 requires at least 3 coins {1, 1, 1}
  53.  
  54.             if (min > (1 + table[sum - change[j]])) {
  55.                 min = 1 + table[sum - change[j]];
  56.             }
  57.         }
  58.         table[sum] = min;
  59.         min = INT32_MAX;
  60.     }
  61.  
  62.     for (i = 0; i <= SUM; i++) {
  63.         printf("SUM[%d]: %d\n", i, table[i]);
  64.     }
  65.  
  66.     return table[SUM];
  67. }
  68.  
  69.  
  70. int main(int argc, const char * argv[])
  71. {
  72.     int change[4] = {1, 5, 10, 25};
  73.     int changeSize = sizeof(change)/sizeof(change[0]);
  74.     int SUM = 16;
  75.  
  76.     printf("MinChange for sum %d = %d\n", SUM, mincount(change, changeSize, SUM));
  77.  
  78.     return 0;
  79. }
Success #stdin #stdout 0s 2248KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
SUM[0]: 0
SUM[1]: 1
SUM[2]: 2
SUM[3]: 3
SUM[4]: 4
SUM[5]: 1
SUM[6]: 2
SUM[7]: 3
SUM[8]: 4
SUM[9]: 5
SUM[10]: 1
SUM[11]: 2
SUM[12]: 3
SUM[13]: 4
SUM[14]: 5
SUM[15]: 2
SUM[16]: 3
MinChange for sum 16 = 3
https://ideone.com/IXJL0d
Min Coin
language:
C (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!