fork download
copy 
  1. #include <iostream>
  2. #include <array>
  3. #include <vector>
  4. #include <list>
  5. #include <algorithm>
  6. #include <memory>
  7. #include <limits>
  8.  
  9. enum CoinType {A, B, C, D, E};  // Any number of coin types are possible in this program.
  10.  
  11. template <std::size_t NumCoinTypes>
  12. class Currency {
  13. 	private:
  14. 		std::array<int, NumCoinTypes> coins;
  15. 	public:
  16. 		Currency() = default;
  17. //		~Currency() {std::cout << "Currency destructor called.\n";}
  18. 		Currency (const std::array<int, NumCoinTypes>& c) : coins(c) {}
  19. 		const std::array<int, NumCoinTypes>& getCoins() const {return coins;}
  20. 		void addCoins (const std::array<int, NumCoinTypes>& coinsAdded) {
  21. 			for (std::size_t i = 0;  i < NumCoinTypes;  i++)
  22. 				coins[i] += coinsAdded[i];
  23. 		}
  24. 		void deductCoins (const std::array<int, NumCoinTypes>& coinsDeducted) {
  25. 			for (std::size_t i = 0;  i < NumCoinTypes;  i++)
  26. 				coins[i] -= coinsDeducted[i];
  27. 		}
  28. 		int numCoins() const {return std::accumulate (coins.begin(), coins.end(), 0);}
  29. 		Currency<NumCoinTypes>* clone() const {return new Currency<NumCoinTypes>(*this);}
  30. 		void print() const {
  31. 			for (int x : coins) std::cout << x << ' ';
  32. 			std::cout << "(total coins = " << numCoins() << ")\n";
  33. 		}
  34. };
  35.  
  36. template <int... CoinValues>
  37. std::array<int, sizeof...(CoinValues)> optimizedChange (int change) {
  38. 	const std::size_t N = sizeof...(CoinValues);  // constexpr
  39. 	std::array<int, N> changeGiven = {0};
  40. 	if (change == 0)
  41. 		return changeGiven;
  42. 	static const std::array<int, N> coinValues = {CoinValues...};
  43. 	std::vector<int> minCoinsNeeded(change+1);  // For each i = 0, 1, ..., change-1, minCoinsNeeded[i] represents the minimum number of coins needed to make change for value i.
  44. 	minCoinsNeeded[0] = 0;
  45. 	minCoinsNeeded[1] = 1;  // Since the cheapest coin has value 1.
  46. 	for (int i = 2; i <= change; i++) {
  47. 		std::vector<int> candidates;
  48. 		for (int c : coinValues)
  49. 			if (c <= i)
  50. 				candidates.push_back (minCoinsNeeded[i-c] + 1);  // 1 coin of value c + the minimum number of coins to get value i-c.
  51. 		minCoinsNeeded[i] = *std::min_element (candidates.begin(), candidates.end());
  52. 	}
  53. 	int v = change;  // With minCoinsNeeded[change] computed, we now compute changeGiven, where changeGiven[i] is the number of the ith coin in the optimized change (0th being the first).
  54. 	while (v > 0) {
  55. 		for (std::size_t i = 0; i < N; i++) {
  56. 			if (coinValues[i] > v)
  57. 				continue;
  58. 			if (minCoinsNeeded[v - coinValues[i]] < minCoinsNeeded[v]) {
  59. 				changeGiven[i]++;
  60. 				v -= coinValues[i];
  61. 				continue;
  62. 			}
  63. 		}
  64. 	}
  65. 	return changeGiven;
  66. }
  67.  
  68. template <std::size_t CoinType, std::size_t N>
  69. int totalAmountHelper (const std::array<int, N>&) {
  70. 	return 0;
  71. }
  72.  
  73. template <std::size_t CoinType, std::size_t N, int First, int... Rest>
  74. int totalAmountHelper (const std::array<int, N>& coins) {
  75. 	return coins[CoinType] * First + totalAmountHelper<CoinType + 1, N, Rest...>(coins);
  76. }
  77.  
  78. template <std::size_t N, int... CoinValues>
  79. int totalAmount (const std::array<int, N>& coins) {
  80. 	return totalAmountHelper<0, N, CoinValues...>(coins);
  81. }
  82.  
  83. template <int... CoinValues>
  84. std::list<std::array<int, sizeof...(CoinValues)>> allSuitablePayments (int price, const std::array<int, sizeof...(CoinValues)>& coinsPossessed) {
  85. 	constexpr std::size_t N = sizeof...(CoinValues);
  86. 	// Let candidates[i] be the list of all arrays representing all the allowable ways to spend the coins to make the purchase of an item of price i, without any redundant coin being given.
  87. 	std::vector<std::list<std::array<int, N>>> candidates(price + 1);
  88. 	for (std::size_t i = 0; i < N; i++) {  // Base case candidates[1].
  89. 		std::array<int, N> singleCoin = {0};
  90. 		singleCoin[i] = 1;  // One coin of each type certainly can pay for an item whose price is 1.
  91. 		candidates[1].emplace_back(singleCoin);
  92. 	}
  93. 	for (int i = 2; i <= price; i++) {
  94. 		for (const std::array<int, N>& x : candidates[i-1]) {
  95. 			const int amount = totalAmount<N, CoinValues...>(x);
  96. 			if (amount >= i) {  // x, which is enough to pay amount i-1, is also enough to pay amount i, so it is inserted in candidates[i].
  97. 				candidates[i].emplace_back(x);
  98. 				continue;
  99. 			}
  100. 			const int amountStillNeeded = i - amount;
  101. 			for (const std::array<int, N>& y : candidates[amountStillNeeded]) {
  102. 				if (totalAmount<N, CoinValues...>(y) >= i)
  103. 					continue;  // Adding any coin to y will make it a redundant coin, so y cannot be used.
  104. 				std::array<int, N> z;  // The possible payments of amountStillNeeded can be "joined" to x, which will then be sufficient to pay amount i.
  105. 				bool allowed = true;
  106. 				for (std::size_t j = 0; j < N; j++) {
  107. 					z[j] = x[j] + y[j];  // z cannot be already an element in candidates[i] because
  108. 					if (z[j] > coinsPossessed[j]) {
  109. 						allowed = false;  // z will certainly be enough to pay the amount i, but it surpasses the amount of coins the customer has.
  110. 						break;
  111. 					}
  112. 				}
  113. 				if (!allowed) continue;
  114. 				for (std::size_t j = 0; j < N; j++) {  // Check if z has any redundant coin.
  115. 					if (z[j] == 0)
  116. 						continue;
  117. 					std::array<int, N> test = z;
  118. 					test[j]--;
  119. 					if (totalAmount<N, CoinValues...>(test) >= i) {
  120. 						allowed = false;  // Removing a coin still results in 'test' being enough to purchase amount i, so 'test' has a redundant coin.
  121. 						break;					
  122. 					}
  123. 				}
  124. 				if (allowed)  // z is sufficient to pay, has no redundant coin, and the customer has enough coins to pay according to z.
  125. 					candidates[i].emplace_back(z);	
  126. 			}
  127. 		}
  128. //		std::cout << "Allowed payments for amount " << i << ":\n";  /////
  129. //		int count = 1;  /////
  130. //		for (const std::array<int, N>& x : candidates[i]) {  /////
  131. //			std::cout << count++ << ":  ";  /////
  132. //			for (int i = 0; i < N; i++)  /////
  133. //				std::cout << x[i] << ' ';  /////
  134. //			std::cout << '\n';  /////
  135. //		}  /////
  136. 	}
  137. 	return candidates[price];
  138. }
  139.  
  140. template <int... CoinValues>
  141. void purchase (int numCoins, CoinType coinType, Currency<sizeof...(CoinValues)>* currency) {  // price = numCoins * coinType's value
  142. 	constexpr std::size_t N = sizeof...(CoinValues);
  143. 	std::cout << "Before paying for the item, currency possessed is: ";  currency->print();
  144. 	static const std::array<int, N> coinValues = {CoinValues...};
  145. 	const int price = numCoins * coinValues[coinType];
  146. 	const std::list<std::array<int, N>> suitablePayments = allSuitablePayments<CoinValues...> (price, currency->getCoins());
  147. 	int min = std::numeric_limits<int>::max();
  148. 	std::array<int, N> optimalPayment, optimalChange;
  149. 	for (const std::array<int, N>& coinsPaid : suitablePayments) {
  150. 		std::unique_ptr<Currency<N>> testCurrency = std::unique_ptr<Currency<N>>(currency->clone());
  151. 		testCurrency->deductCoins (coinsPaid);
  152. 		const int totalPaid = totalAmount<N, CoinValues...>(coinsPaid);
  153. 		const int change = totalPaid - price;
  154. 		const std::array<int, N> coinsReturned = optimizedChange<CoinValues...>(change);
  155. 		testCurrency->addCoins (coinsReturned);
  156. //		std::cout << "Price of item = " << price << '\n';
  157. //		std::cout << "Coins paid: ";  for (int x : coinsPaid) std::cout << x << ' ';  std::cout << '\n';
  158. //		std::cout << "Total amount paid = " << totalPaid << '\n';
  159. //		std::cout << "Total change = " << change << '\n';
  160. //		std::cout << "Coins returned as change: ";  for (int x : coinsReturned) std::cout << x << ' ';  std::cout << '\n';
  161. //		std::cout << "After paying for the item, currency possessed is: ";  testCurrency->print();
  162. 		if (testCurrency->numCoins() < min) {
  163. 			min = testCurrency->numCoins();
  164. 			optimalPayment = coinsPaid;
  165. 			optimalChange = coinsReturned;
  166. 		}
  167. 	}
  168. 	currency->deductCoins (optimalPayment);
  169. 	currency->addCoins (optimalChange);
  170. 	std::cout << "\nFinal solution:\n";
  171. 	std::cout << "Price of item = " << price << '\n';
  172. 	std::cout << "Coins paid: ";  for (int x : optimalPayment) std::cout << x << ' ';  std::cout << '\n';
  173. 	std::cout << "Coins returned as change: ";  for (int x : optimalChange) std::cout << x << ' ';  std::cout << '\n';
  174. 	std::cout << "After paying for the item, currency possessed is: ";  currency->print();
  175. }
  176.  
  177. int main() {
  178. //	const std::list<std::array<int, 5>> suitablePayments = allSuitablePayments<1,10,25,50,100>(60, {6,3,2,2,2});  // 6 possibilities
  179. //	const std::list<std::array<int, 5>> suitablePayments = allSuitablePayments<1,10,25,50,100>(151, {30,4,5,2,1});  // 37 possibilities
  180. //	int i = 1;
  181. //	for (const std::array<int, 5>& array : suitablePayments) {
  182. //		std::cout << i++ << ":  ";
  183. //		for (int x : array)
  184. //			std::cout << x << ' ';
  185. //		std::cout << '\n';
  186. //	}
  187. 	std::cout << "Value of each coin: 1, 10, 25, 50, 100\n";
  188. 	purchase<1,10,25,50,100>(151, A, new Currency<5>({30,4,5,2,1}));  // Output agrees with previous.
  189.  
  190. 	std::cout << "\n\nValue of each coin: 1, 12, 65, 125, 200\n";
  191. 	purchase<1,12,65,125,200>(157, A, new Currency<5>({2,4,6,2,1}));  // Output agrees with previous.
  192.  
  193. 	std::cout << "\n\nValue of each coin: 1, 12, 65, 125, 200\n";
  194. 	purchase<1,12,65,125,200>(157, A, new Currency<5>({100,100,100,100,100}));  // Very fast, because the increase in the number of coins the customer has makes no difference in the time complexity.
  195. }
Success #stdin #stdout 0s 3280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Value of each coin: 1, 10, 25, 50, 100
Before paying for the item, currency possessed is: 30 4 5 2 1 (total coins = 42)

Final solution:
Price of item = 151
Coins paid: 26 0 5 0 0 
Coins returned as change: 0 0 0 0 0 
After paying for the item, currency possessed is: 4 4 0 2 1 (total coins = 11)


Value of each coin: 1, 12, 65, 125, 200
Before paying for the item, currency possessed is: 2 4 6 2 1 (total coins = 15)

Final solution:
Price of item = 157
Coins paid: 0 3 0 1 0 
Coins returned as change: 4 0 0 0 0 
After paying for the item, currency possessed is: 6 1 6 1 1 (total coins = 15)


Value of each coin: 1, 12, 65, 125, 200
Before paying for the item, currency possessed is: 100 100 100 100 100 (total coins = 500)

Final solution:
Price of item = 157
Coins paid: 97 5 0 0 0 
Coins returned as change: 0 0 0 0 0 
After paying for the item, currency possessed is: 3 95 100 100 100 (total coins = 398)
https://ideone.com/A1nUD2
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!