c++編程Coin Changing

#include <vector>

#include <algorithm>

#include <string>

#include <iostream>

using namespace std;

int needCoins(vector<int>& T, vector<int>& Coins, int m)

{

if(m==0) return 0;

int k = 200000; //maximum

for(int i=0; i<Coins.size(); i++) {

if(Coins[i]>0 && m-T[i]>=0) {

vector<int> newCoins(Coins.begin(), Coins.end()); //a copy

newCoins[i]--;

int t = needCoins(T, newCoins, m-T[i]);

if(t!= -1 && k > t+1) k = t+1;

}

}

if(k==200000) return -1;

else return k;

}

int _tmain(int argc, _TCHAR* argv[])

{

vector<int> T;

T.push_back(1);

T.push_back(2);

T.push_back(5);

vector<int> Coins;

Coins.push_back(3);

Coins.push_back(2);

Coins.push_back(2);

int ret = needCoins(T, Coins, 8);

cout << ret << endl;

return 0;

}