Taraxacum

how many coins

Dec 1st, 2021
660
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <cstddef>
  2. #include <cstdint>
  3. #include <cstdio>
  4. #include <iostream>
  5. #include <vector>
  6.  
  7. constexpr unsigned COINS[] = {1, 5, 16, 23, 33};
  8. constexpr unsigned COINS_CNT = sizeof(COINS) / sizeof(unsigned);
  9.  
  10. unsigned greedy(unsigned amount) {
  11.     unsigned cnt[COINS_CNT] = {0};
  12.  
  13.     for (int i = COINS_CNT - 1; i >= 0; i--) {
  14.         cnt[i] = amount / COINS[i];
  15.         amount %= COINS[i];
  16.     }
  17.  
  18.     unsigned sum = 0;
  19.     for (size_t i = 0; i < COINS_CNT; i++) {
  20.         sum += cnt[i];
  21.         printf("%u * %u\t", cnt[i], COINS[i]);
  22.     }
  23.  
  24.     return sum;
  25. }
  26.  
  27. std::pair<unsigned, std::vector<unsigned>>
  28. exhaustive_internal(unsigned amount, size_t coin_index) {
  29.     unsigned coin = COINS[coin_index];
  30.     unsigned max_cnt = amount / coin;
  31.     unsigned min_cnt = UINT32_MAX;
  32.     std::vector<unsigned> min_result;
  33.  
  34.     if (coin_index == 0) {
  35.         if (amount % coin == 0) {
  36.             return {max_cnt, {max_cnt}};
  37.         } else {
  38.             return {min_cnt, {}};
  39.         }
  40.     }
  41.  
  42.     for (size_t i = 0; i <= max_cnt; i++) {
  43.         auto [min, result] =
  44.             exhaustive_internal(amount - i * coin, coin_index - 1);
  45.         if (min < min_cnt && min + i < min_cnt) {
  46.             min_cnt = min + i;
  47.             result.push_back(i);
  48.             min_result = result;
  49.         }
  50.     }
  51.  
  52.     return {min_cnt, min_result};
  53. }
  54.  
  55. unsigned exhaustive(unsigned amount) {
  56.     auto [min, min_result] = exhaustive_internal(amount, COINS_CNT - 1);
  57.  
  58.     for (size_t i = 0; i < COINS_CNT; i++) {
  59.         printf("%u * %u\t", min_result[i], COINS[i]);
  60.     }
  61.  
  62.     return min;
  63. }
  64.  
  65. int main() {
  66.     for (unsigned amount = 1; amount < 100; amount++) {
  67.         std::cout << "========== " << amount << " ==========" << std::endl;
  68.         std::cout << greedy(amount) << std::endl;
  69.         std::cout << exhaustive(amount) << std::endl;
  70.     }
  71. }
  72.  
RAW Paste Data