[ITSA] ITSA 56 Problem 3. 零錢兌換

題目

Link: 零錢兌換

Sample input

2
1000 600 11 2 1 98654
600 22 3 1 54321

Sample output

108
1000 98
600 1
11 4
2 5
1 0
109
600 90
22 14
3 4
1 1

Hint

Dynamic Programming (動態規劃)

Code

C++

//#include <cstdint>
#include <iostream>
#include <vector>
#include <algorithm>

#ifndef INT32_MAX
  #define INT32_MAX 0x7fffffff
#endif

struct DP
{
    int32_t total;
    std::vector<int32_t> types;
    explicit DP(size_t size) : total(INT32_MAX), types(size) {}
};

int32_t main()
{
  int32_t i;

  int32_t test_cases;
  std::vector<int32_t> types;
  int32_t temp, target_value, num_of_types, current;

  std::vector<DP> dp;

  // free I/O synchronization
  std::ios::sync_with_stdio(false);

  std::cin >> test_cases;

  while (test_cases--)
  {
    types.clear();
    do
    {
      std::cin >> temp;
      types.push_back(temp);
    } while (temp != 1);
    std::sort(types.begin(), types.end(), [=] (int32_t a, int32_t b) -> bool { return a > b; });
    num_of_types = static_cast<int32_t>(types.size());

    std::cin >> target_value;

    dp.clear();
    dp.resize(static_cast<uint64_t>(target_value) + 1, DP(types.size()));
    dp[0].total = 0;

    for (current = 0; current < target_value; ++current)
    {
      for (i = 0; i < num_of_types; ++i)
      {
        if (dp[current].total != INT32_MAX)
        {
          temp = current + types[i];
          if (temp <= target_value and dp[temp].total > dp[current].total + 1)
          {
            dp[temp].total = dp[current].total + 1;
            dp[temp].types = dp[current].types;
            ++dp[temp].types[i];
          }
        }
      }
    }

    std::cout << dp[target_value].total << std::endl;
    for (i = 0; i < num_of_types; ++i)
      std::cout << types[i] << " " << dp[target_value].types[i] << std::endl;
  }

  return 0;
}

Show Comments