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

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

题面：设有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条）