19 bool operator()(
const OutputGroup& a,
const OutputGroup& b)
const
21 return a.GetSelectionAmount() > b.GetSelectionAmount();
70 std::vector<bool> curr_selection;
71 curr_selection.reserve(utxo_pool.size());
74 CAmount curr_available_value = 0;
77 assert(utxo.GetSelectionAmount() > 0);
78 curr_available_value += utxo.GetSelectionAmount();
80 if (curr_available_value < selection_target) {
85 std::sort(utxo_pool.begin(), utxo_pool.end(),
descending);
88 std::vector<bool> best_selection;
94 bool backtrack =
false;
95 if (curr_value + curr_available_value < selection_target ||
96 curr_value > selection_target + cost_of_change ||
97 (curr_waste > best_waste && (utxo_pool.at(0).fee - utxo_pool.at(0).long_term_fee) > 0)) {
99 }
else if (curr_value >= selection_target) {
100 curr_waste += (curr_value - selection_target);
105 if (curr_waste <= best_waste) {
106 best_selection = curr_selection;
107 best_selection.resize(utxo_pool.size());
108 best_waste = curr_waste;
109 if (best_waste == 0) {
113 curr_waste -= (curr_value - selection_target);
120 while (!curr_selection.empty() && !curr_selection.back()) {
121 curr_selection.pop_back();
122 curr_available_value += utxo_pool.at(curr_selection.size()).GetSelectionAmount();
125 if (curr_selection.empty()) {
130 curr_selection.back() =
false;
131 OutputGroup& utxo = utxo_pool.at(curr_selection.size() - 1);
135 OutputGroup& utxo = utxo_pool.at(curr_selection.size());
142 if (!curr_selection.empty() && !curr_selection.back() &&
143 utxo.
GetSelectionAmount() == utxo_pool.at(curr_selection.size() - 1).GetSelectionAmount() &&
144 utxo.
fee == utxo_pool.at(curr_selection.size() - 1).fee) {
145 curr_selection.push_back(
false);
148 curr_selection.push_back(
true);
156 if (best_selection.empty()) {
161 for (
size_t i = 0; i < best_selection.size(); ++i) {
162 if (best_selection.at(i)) {
174 std::vector<size_t> indexes;
175 indexes.resize(utxo_pool.size());
176 std::iota(indexes.begin(), indexes.end(), 0);
179 CAmount selected_eff_value = 0;
180 for (
const size_t i : indexes) {
185 if (selected_eff_value >= target_value) {
193 std::vector<char>& vfBest,
CAmount& nBest,
int iterations = 1000)
195 std::vector<char> vfIncluded;
197 vfBest.assign(groups.size(),
true);
202 for (
int nRep = 0; nRep < iterations && nBest != nTargetValue; nRep++)
204 vfIncluded.assign(groups.size(),
false);
206 bool fReachedTarget =
false;
207 for (
int nPass = 0; nPass < 2 && !fReachedTarget; nPass++)
209 for (
unsigned int i = 0; i < groups.size(); i++)
217 if (nPass == 0 ? insecure_rand.
randbool() : !vfIncluded[i])
219 nTotal += groups[i].GetSelectionAmount();
220 vfIncluded[i] =
true;
221 if (nTotal >= nTargetValue)
223 fReachedTarget =
true;
229 nTotal -= groups[i].GetSelectionAmount();
230 vfIncluded[i] =
false;
243 std::optional<OutputGroup> lowest_larger;
244 std::vector<OutputGroup> applicable_groups;
250 if (group.GetSelectionAmount() == nTargetValue) {
253 }
else if (group.GetSelectionAmount() < nTargetValue +
MIN_CHANGE) {
254 applicable_groups.push_back(group);
255 nTotalLower += group.GetSelectionAmount();
256 }
else if (!lowest_larger || group.GetSelectionAmount() < lowest_larger->GetSelectionAmount()) {
257 lowest_larger = group;
261 if (nTotalLower == nTargetValue) {
262 for (
const auto& group : applicable_groups) {
268 if (nTotalLower < nTargetValue) {
269 if (!lowest_larger)
return std::nullopt;
275 std::sort(applicable_groups.begin(), applicable_groups.end(),
descending);
276 std::vector<char> vfBest;
280 if (nBest != nTargetValue && nTotalLower >= nTargetValue +
MIN_CHANGE) {
287 ((nBest != nTargetValue && nBest < nTargetValue +
MIN_CHANGE) || lowest_larger->GetSelectionAmount() <= nBest)) {
290 for (
unsigned int i = 0; i < applicable_groups.size(); i++) {
292 result.
AddInput(applicable_groups[i]);
297 std::string log_message{
"Coin selection best subset: "};
298 for (
unsigned int i = 0; i < applicable_groups.size(); i++) {
322 if (positive_only && ev <= 0)
return;
327 coin.
m_fee = coin_fee;
367 CAmount selected_effective_value = 0;
369 waste += coin.m_fee - coin.m_long_term_fee;
370 selected_effective_value += use_effective_value ? coin.effective_value : coin.txout.nValue;
377 waste += change_cost;
380 assert(selected_effective_value >= target);
381 waste += selected_effective_value - target;