#include "stdio.h" #include "stdlib.h" #include "string.h" #include "math.h" #include "iostream.h" class node { public: int* BestMakeUp; int NumOfCoins; node() { BestMakeUp = NULL; NumOfCoins = 0; } ~node() { delete BestMakeUp; } node(int m) { BestMakeUp = new int[m]; for(int i = 0; i < m; i ++) { BestMakeUp[i] = 0; } NumOfCoins = 0; } }; void MakeBestChange(node** BC, int sizeBC, int* CV, int sizeCV) { BC[1]->BestMakeUp[0]++; BC[1]->NumOfCoins++; for(int i = 2; i < sizeBC; i++) { int MaxNumOfCoins = 5000; int index; int indexOfBestCoinToAdd ; int indexOfBestNode = 0; for(int j = 0; j < sizeCV; j++) { index = i - CV[j]; if((index >= 0) &&(BC[index]->NumOfCoins + 1) < (MaxNumOfCoins)) { indexOfBestCoinToAdd = j; indexOfBestNode = index; MaxNumOfCoins = BC[index]->NumOfCoins + 1; for(int k = 0; k < sizeCV; k++) { BC[i]->BestMakeUp[k] = BC[index]->BestMakeUp[k]; } } } BC[i]->BestMakeUp[indexOfBestCoinToAdd]++; BC[i]->NumOfCoins = BC[indexOfBestNode]->NumOfCoins + 1; } } void main() { int NumOfDataSets; int m; int n; cin >> NumOfDataSets; for(int i = 0; i < NumOfDataSets; i++) { cin >> m; cin >> n; //Input Coins Values int* CoinValues = new int[m]; for(int j = 0; j < m; j++) cin >> CoinValues[j]; cout << "Data Set " << i + 1 << endl; //Input Values node** BestChange = new node*[5001]; for(int l = 0; l < 5001; l ++) BestChange[l] = new node(m); MakeBestChange(BestChange, 5001, CoinValues, m); for (int k = 0; k < n; k++) { int MakeChangeOf; cin >> MakeChangeOf; cout << "U" << MakeChangeOf << " = "; for(int i = 0; i < m; i++) { cout << BestChange[MakeChangeOf]->BestMakeUp[i] << " "; } cout << "\n"; } delete []BestChange; delete CoinValues; } }