[数据结构与算法]数据结构与算法-最少硬币问题

• 题面：设有n 种不同面值的硬币，各硬币的面值存于数组T［1:n ］中。现要用这些面值的硬币来找钱。可以使用的各种面值的硬币个数存于数组Coins［1:n ］中。对任意钱数0≤m≤20001，设计一个用最少硬币找钱m 的方法。

• 数据输入：由文件input.txt 提供输入数据，文件的第一行中只有1 个整数给出n 的值,第2 行起每行2 个数，分别是T[j] 和Coins[j] 。最后1 行是要找的钱数m。

• 数据输出：程序运行结束时，将计算出的最少硬币数输出到文件output.txt 中。问题无解时输出-1。

• 样例输入：
  3

  1 3

  2 3

  5 3

  18

• 样例输出： 5

• 代码

  /**
  * 请不要质疑1+1=2
   */
  #include <iostream>
  #include <iomanip>
  #include <algorithm>  //sort
  #include <map>
  #include <queue>
  #include <deque>  //双端队列，头可插，尾可插
  #include <string>
  #include <cstring>
  #include <stack>
  #include <cmath>
  #include <fstream>
  #include <ctime>
  #include <climits> //数值的限制范围
  //(double)clock() / CLOCKS_PER_SEC <= 0.95 限制0.95s跑完
  using namespace std;
  
  class Solver {
      //通用属性
  public:
      string name;
      bool isDebug;
  
      Solver(const string name, const bool isDebug) {
          this->name = name;
          this->isDebug = isDebug;
      }
  
      //通用方法
  protected:
      static int QuickRead() {
          int num = 0, flag = 1;
          char ch = getchar();
          //读符号
          while (ch < '0' || ch > '9') {
              if (ch == '-') {
                  flag = -1;
              }
              ch = getchar();
          }
          //读数值
          while (ch >= '0' && ch <= '9') {
              num = (num << 1) + (num << 3) + (ch ^ 48);
              ch = getchar();
          }
          return flag * num;
      }
  
  public:
      void SaveCpp() const {
  
          fstream input;
          fstream output;
  
          input.open("moota.cpp", ios::in);
          const string file = name + ".cpp";
          output.open(file.c_str(), ios::out);
  
          char c = 'O';
          while (!input.eof()) {
              input.get(c);
              output << c;
          }
  
          input.close();
          output.close();
  
      }
  
      void Debug(const string message) const {
          if (isDebug) { cout << message; }
      }
  
  protected:
      //待实现方法
      virtual void BeginPlay() {
          Debug("\n---BeginPlay---\n");
      };
  
      virtual void Playing() {
          Debug("\n---Playing---\n");
      };
  
      virtual void EndPlay() {
          Debug("\n---EndPlay---\n");
      };
  public:
      //外观模式
      void Play() {
          BeginPlay();
          Playing();
          EndPlay();
      }
  };
  
  class Player {
  private:
      string name;
  public:
      Player(const string name) {
          this->name = name;
      }
  
      void Play(Solver* solver) const {
          if (solver->isDebug) {
              cout << "\n" << name << "开始做题\n";
              solver->SaveCpp();
          }
          solver->Play();
      }
  };
  
  class SpecialSolver : public Solver {
  public:
      static const int MAX = int(1e7);
      static const long long INF = (long long)1e18;
  
      SpecialSolver(const string name, const bool isDebug): Solver(name, isDebug) {
      }
  
  private: //实例属性
      int n, m;
  
      struct Node {
          int value;
          int num;
      } node[20];
  
      int dp[1000];
  private: //实例方法
      void Dp() {
          for (int i = 1; i <= m; ++i) {
              dp[i] = MAX;
          }
          //i:硬币编号
          for (int i = 1; i <= n; ++i) {
              int num = node[i].num;
              //j:使用硬币数
              for (int j = 1; j <= num; ++j) {
                  //k:当前总价值
                  for (int k = m; k >= node[i].value * j; --k) {
                      dp[k] = min(dp[k], dp[k - node[i].value * j] + j);
                  }
              }
          }
      }
  
  protected
  :
      virtual void BeginPlay() override {
          Solver::BeginPlay();
          cin >> n;
          for (int i = 1; i <= n; ++i) {
              cin >> node[i].value >> node[i].num;
          }
          cin >> m;
      };
  
      virtual void Playing() override {
          Solver::Playing();
          Dp();
      };
  
      virtual void EndPlay() override {
          Solver::EndPlay();
          if (dp[m] != MAX) {
              cout << dp[m];
          }
          else {
              cout << "-1";
          }
  
      };
  };
  
  //注意改名字和状态
  Player player("moota");
  SpecialSolver specialSolver("最少硬币问题", false);
  
  int main() {
      player.Play(&specialSolver);
  }