algorithm - test2

Question

輸入一個金額 dst，列出最佳找法。

Anwser

程式思路:

用 BFS 直接展開解

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

void printpath(vector<int>& path) {
    int size = path.size();
    for (int i = 1; i < size; i++) {
        cout << path[i] - path[i - 1] << " ";
    }
    cout << " use " << size - 1 << " coins";
    cout << endl;
}

int isNotVisited(int x, vector<int>& path) {
    int size = path.size();
    for (int i = 0; i < size; i++)
        if (path[i] == x)
            return 0;
    return 1;
}

int solution(int dst) {
    int coin[3] = { 1,5,10};
    int ways = 0;
    vector<int> visited;
    vector<int> path;
    queue < vector<int> > q;

    path.push_back(0);
    q.push(path);

    while (!q.empty()) {
        path = q.front();
        q.pop();

        int last = path[path.size() - 1];
        if (last == dst) {
            printpath(path);
            ways++;
            break;
        }

        for (int i = 0; i < 3; i++) {
            int sum = coin[i] + last;

            if (sum > dst) {
                break;
            }
            if (isNotVisited(sum, path)) {
                vector<int> newpath(path);
                newpath.push_back(sum);
                q.push(newpath);
            }
        }
    }
    return ways;
}
#define TEST(x) printf("------------\n",x,solution(x));
int main(int argc, char* argv[]) {
    TEST(13);
    TEST(16);
    TEST(23);
    return 0;
}

Result

1 1 1 10  use 4 coins
------------
1 5 10  use 3 coins
------------
1 1 1 10 10  use 5 coins
------------