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

数据结构与算法-最少硬币问题,第1张

数据结构与算法-最少硬币问题
  • 题面:设有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

  • 代码

    #include 
    #include 
    #include   //sort
    #include 
    #include 
    #include   //双端队列,头可插,尾可插
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include  //数值的限制范围
    //(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);
    }
    
    

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/5579664.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-14
下一篇 2022-12-14

发表评论

登录后才能评论

评论列表(0条)

保存