fork(1) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <tuple>
  4. #include <limits>
  5. #include <algorithm>
  6. #include <cstdint>
  7. #include <cmath>
  8. #include <iomanip>
  9.  
  10. typedef std::tuple<std::uint64_t, double> Coin;
  11. typedef std::vector<Coin> Coins;
  12. typedef std::vector<std::uint64_t> DType;
  13. typedef std::vector<DType> RType;
  14.  
  15. bool DoubleEqual(double a, double b,double Epsilon){
  16. 	return std::abs(a - b) <= Epsilon;
  17. }
  18.  
  19. bool AddVector(DType& D, DType& L){
  20. 	bool Carry = false;
  21. 	D[0]++;
  22. 	for (std::size_t i = 0; i < D.size(); i++)
  23. 	{
  24. 		if (Carry == true){
  25. 			D[i]++;
  26. 		}
  27. 		Carry = false;
  28. 		if (D[i] > L[i]){
  29. 			D[i] = 0;
  30. 			Carry = true;
  31. 		}
  32.  
  33. 	}
  34. 	return true;
  35. }
  36.  
  37. bool CheckWeight(const double& Weight, Coins& C, DType& D){
  38.  
  39. 	double Total = 0;
  40.  
  41. 	for (std::size_t i = 0; i < C.size(); i++){
  42. 		Total += std::get<1>(C[i]) * D[i];
  43. 	}
  44.  
  45. 	return DoubleEqual(Weight, Total,0.000000001);
  46. }
  47.  
  48.  
  49. RType MakeHoge(double Weight, Coins C){
  50. 	DType L;
  51. 	DType D(C.size());
  52. 	bool F = false;
  53. 	RType R;
  54. 	for (auto& o : C){
  55. 		L.push_back(static_cast<std::uint64_t>(std::ceil(Weight / std::get<1>(o))));
  56. 	}
  57.  
  58. 	while (F == false){
  59. 		if (CheckWeight(Weight, C, D) == true){
  60. 			R.push_back(D);
  61. 		}
  62.  
  63. 		AddVector(D, L);
  64.  
  65. 		F = true;
  66. 		for (std::size_t i = 0; i < D.size(); i++)
  67. 		{
  68. 			if (D[i] != L[i]){
  69. 				F = false;
  70. 				break;
  71. 			}
  72.  
  73. 		}
  74. 	}
  75.  
  76. 	return R;
  77. }
  78.  
  79. bool Show(const double& Weight, RType R, Coins C){
  80. 	double Total = 0;
  81.  
  82. 	std::cout << "input Weight:" << Weight <<"g"<< std::endl;
  83. 	std::cout << "have the " << R.size()<<" Lists"<< std::endl;
  84. 	std::cout << std::setw(10)<<"amount|";
  85. 	for (auto& o : C){
  86. 		std::cout << std::setw(5)<<std::get<0>(o);
  87. 	}
  88.  
  89. 	std::cout<<std::endl;
  90.  
  91. 	std::sort(R.begin(), R.end(), [&](DType& A, DType& B){
  92. 		double TotalA = 0;
  93. 		double TotalB = 0;
  94. 		for (std::size_t i = 0; i < A.size(); i++)
  95. 		{
  96. 			TotalA += A[i] * std::get<0>(C[i]);
  97. 		}
  98. 		for (std::size_t i = 0; i < B.size(); i++)
  99. 		{
  100. 			TotalB += B[i] * std::get<0>(C[i]);
  101. 		}
  102. 		return TotalA < TotalB;
  103. 	});
  104.  
  105. 	for (auto& oo : R){
  106. 		for (std::size_t i = 0; i < oo.size(); i++)
  107. 		{
  108. 			Total += oo[i] * std::get<0>(C[i]);
  109. 		}
  110. 		std::cout << std::setw(9) << Total<<"|";
  111. 		for (auto& o : oo){
  112. 			std::cout << std::setw(5) << o;
  113. 		}
  114. 		std::cout<<std::endl;
  115. 		Total = 0;
  116. 	}
  117.  
  118.  
  119. 	return true;
  120. }
  121.  
  122.  
  123. int main(){
  124. 	Coins C{ std::make_tuple(1, 1.0), std::make_tuple(5, 3.7), std::make_tuple(10, 4.5), std::make_tuple(50, 4.0), std::make_tuple(100, 4.8), std::make_tuple(500, 7.0), };
  125. 	double W = 0;
  126. 	RType R;
  127.  
  128. 	W = 23.7;
  129. 	R = MakeHoge(W, C);
  130. 	Show(W, R, C);
  131.  
  132. 	return 0;
  133.  
  134. }
Success #stdin #stdout 0.01s 3284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
input Weight:23.7g
have the 23 Lists
   amount|    1    5   10   50  100  500
       25|   20    1    0    0    0    0
       36|   11    1    2    0    0    0
       47|    2    1    4    0    0    0
       71|   16    1    0    1    0    0
       82|    7    1    2    1    0    0
      117|   12    1    0    2    0    0
      127|    7    2    1    0    1    0
      128|    3    1    2    2    0    0
      163|    8    1    0    3    0    0
      173|    3    2    1    1    1    0
      209|    4    1    0    4    0    0
      218|    3    3    0    0    2    0
      255|    0    1    0    5    0    0
      410|    0    0    1    0    4    0
      518|   13    1    0    0    0    1
      529|    4    1    2    0    0    1
      564|    9    1    0    1    0    1
      575|    0    1    2    1    0    1
      610|    5    1    0    2    0    1
      620|    0    2    1    0    1    1
      656|    1    1    0    3    0    1
     1011|    6    1    0    0    0    2
     1057|    2    1    0    1    0    2
https://ideone.com/JeUEIU
language:
C++14 (gcc 8.3)
created:
9 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!