72 const Amount &target_value,
const Amount &cost_of_change,
73 std::set<CInputCoin> &out_set,
Amount &value_ret,
74 const Amount not_input_fees) {
79 std::vector<bool> curr_selection;
80 curr_selection.reserve(utxo_pool.size());
81 Amount actual_target = not_input_fees + target_value;
89 curr_available_value += utxo.effective_value;
91 if (curr_available_value < actual_target) {
96 std::sort(utxo_pool.begin(), utxo_pool.end(),
descending);
99 std::vector<bool> best_selection;
105 bool backtrack =
false;
106 if (curr_value + curr_available_value <
113 (curr_waste > best_waste &&
114 (utxo_pool.at(0).fee - utxo_pool.at(0).long_term_fee) >
122 else if (curr_value >= actual_target) {
131 curr_waste += (curr_value - actual_target);
133 if (curr_waste <= best_waste) {
134 best_selection = curr_selection;
135 best_selection.resize(utxo_pool.size());
136 best_waste = curr_waste;
143 curr_waste -= (curr_value - actual_target);
151 while (!curr_selection.empty() && !curr_selection.back()) {
152 curr_selection.pop_back();
153 curr_available_value +=
154 utxo_pool.at(curr_selection.size()).effective_value;
157 if (curr_selection.empty()) {
164 curr_selection.back() =
false;
165 OutputGroup &utxo = utxo_pool.at(curr_selection.size() - 1);
172 OutputGroup &utxo = utxo_pool.at(curr_selection.size());
181 if (!curr_selection.empty() && !curr_selection.back() &&
183 utxo_pool.at(curr_selection.size() - 1).effective_value &&
184 utxo.
fee == utxo_pool.at(curr_selection.size() - 1).fee) {
185 curr_selection.push_back(
false);
188 curr_selection.push_back(
true);
196 if (best_selection.empty()) {
202 for (
size_t i = 0; i < best_selection.size(); ++i) {
203 if (best_selection.at(i)) {
205 value_ret += utxo_pool.at(i).m_value;
213 const Amount &nTotalLower,
214 const Amount &nTargetValue,
215 std::vector<char> &vfBest,
Amount &nBest,
216 int iterations = 1000) {
217 std::vector<char> vfIncluded;
219 vfBest.assign(groups.size(),
true);
224 for (
int nRep = 0; nRep < iterations && nBest != nTargetValue; nRep++) {
225 vfIncluded.assign(groups.size(),
false);
227 bool fReachedTarget =
false;
228 for (
int nPass = 0; nPass < 2 && !fReachedTarget; nPass++) {
229 for (
size_t i = 0; i < groups.size(); i++) {
235 if (nPass == 0 ? insecure_rand.
randbool() : !vfIncluded[i]) {
236 nTotal += groups[i].m_value;
237 vfIncluded[i] =
true;
238 if (nTotal >= nTargetValue) {
239 fReachedTarget =
true;
240 if (nTotal < nBest) {
245 nTotal -= groups[i].m_value;
246 vfIncluded[i] =
false;
255 std::set<CInputCoin> &setCoinsRet,
Amount &nValueRet) {
260 std::optional<OutputGroup> lowest_larger;
261 std::vector<OutputGroup> applicable_groups;
267 if (group.m_value == nTargetValue) {
269 nValueRet += group.m_value;
271 }
else if (group.m_value < nTargetValue +
MIN_CHANGE) {
272 applicable_groups.push_back(group);
273 nTotalLower += group.m_value;
274 }
else if (!lowest_larger || group.m_value < lowest_larger->m_value) {
275 lowest_larger = group;
279 if (nTotalLower == nTargetValue) {
280 for (
const auto &group : applicable_groups) {
282 nValueRet += group.m_value;
287 if (nTotalLower < nTargetValue) {
288 if (!lowest_larger) {
292 nValueRet += lowest_larger->m_value;
297 std::sort(applicable_groups.begin(), applicable_groups.end(),
descending);
298 std::vector<char> vfBest;
303 if (nBest != nTargetValue && nTotalLower >= nTargetValue +
MIN_CHANGE) {
312 ((nBest != nTargetValue && nBest < nTargetValue +
MIN_CHANGE) ||
313 lowest_larger->m_value <= nBest)) {
315 nValueRet += lowest_larger->m_value;
317 for (
size_t i = 0; i < applicable_groups.size(); i++) {
319 util::insert(setCoinsRet, applicable_groups[i].m_outputs);
320 nValueRet += applicable_groups[i].m_value;
327 "SelectCoins() best subset: ");
328 for (
size_t i = 0; i < applicable_groups.size(); i++) {
350 bool positive_only) {
366 coin.
m_fee = coin_fee;
static constexpr Amount MAX_MONEY
No amount larger than this (in satoshi) is valid.
Amount GetFee(size_t nBytes) const
Return the fee in satoshis for the given size in bytes.
bool randbool() noexcept
Generate a random boolean.
static void ApproximateBestSubset(const std::vector< OutputGroup > &groups, const Amount &nTotalLower, const Amount &nTargetValue, std::vector< char > &vfBest, Amount &nBest, int iterations=1000)
static const size_t TOTAL_TRIES
bool KnapsackSolver(const Amount nTargetValue, std::vector< OutputGroup > &groups, std::set< CInputCoin > &setCoinsRet, Amount &nValueRet)
bool SelectCoinsBnB(std::vector< OutputGroup > &utxo_pool, const Amount &target_value, const Amount &cost_of_change, std::set< CInputCoin > &out_set, Amount &value_ret, const Amount not_input_fees)
This is the Branch and Bound Coin Selection algorithm designed by Murch.
static constexpr Amount MIN_CHANGE
target minimum change amount
static bool LogAcceptCategory(BCLog::LogFlags category)
Return true if log accepts specified category.
#define LogPrint(category,...)
#define LogPrintToBeContinued
std::string FormatMoney(const Amount amt)
Do not use these functions to represent or parse monetary amounts to or from JSON but use AmountFromV...
void insert(Tdst &dst, const Tsrc &src)
Simplification of std insertion.
void Shuffle(I first, I last, R &&rng)
More efficient than using std::shuffle on a FastRandomContext.
static constexpr Amount zero() noexcept
const int conf_theirs
Minimum number of confirmations for outputs received from a different wallet.
std::vector< CInputCoin > m_outputs
CFeeRate m_long_term_feerate
CFeeRate m_effective_feerate
void Insert(const CInputCoin &output, int depth, bool from_me, bool positive_only)
bool EligibleForSpending(const CoinEligibilityFilter &eligibility_filter) const