1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
crate::ix!();
/**
| Original coin selection algorithm
| as a fallback
|
*/
pub fn knapsack_solver(
n_target_value: &Amount,
groups: &mut Vec<OutputGroup>,
set_coins_ret: &mut HashSet<InputCoin>,
n_value_ret: &mut Amount) -> bool {
todo!();
/*
setCoinsRet.clear();
nValueRet = 0;
// List of values less than target
std::optional<OutputGroup> lowest_larger;
std::vector<OutputGroup> applicable_groups;
CAmount nTotalLower = 0;
Shuffle(groups.begin(), groups.end(), FastRandomContext());
for (const OutputGroup& group : groups) {
if (group.GetSelectionAmount() == nTargetValue) {
util::insert(setCoinsRet, group.m_outputs);
nValueRet += group.m_value;
return true;
} else if (group.GetSelectionAmount() < nTargetValue + MIN_CHANGE) {
applicable_groups.push_back(group);
nTotalLower += group.GetSelectionAmount();
} else if (!lowest_larger || group.GetSelectionAmount() < lowest_larger->GetSelectionAmount()) {
lowest_larger = group;
}
}
if (nTotalLower == nTargetValue) {
for (const auto& group : applicable_groups) {
util::insert(setCoinsRet, group.m_outputs);
nValueRet += group.m_value;
}
return true;
}
if (nTotalLower < nTargetValue) {
if (!lowest_larger) return false;
util::insert(setCoinsRet, lowest_larger->m_outputs);
nValueRet += lowest_larger->m_value;
return true;
}
// Solve subset sum by stochastic approximation
std::sort(applicable_groups.begin(), applicable_groups.end(), descending);
std::vector<char> vfBest;
CAmount nBest;
ApproximateBestSubset(applicable_groups, nTotalLower, nTargetValue, vfBest, nBest);
if (nBest != nTargetValue && nTotalLower >= nTargetValue + MIN_CHANGE) {
ApproximateBestSubset(applicable_groups, nTotalLower, nTargetValue + MIN_CHANGE, vfBest, nBest);
}
// If we have a bigger coin and (either the stochastic approximation didn't find a good solution,
// or the next bigger coin is closer), return the bigger coin
if (lowest_larger &&
((nBest != nTargetValue && nBest < nTargetValue + MIN_CHANGE) || lowest_larger->GetSelectionAmount() <= nBest)) {
util::insert(setCoinsRet, lowest_larger->m_outputs);
nValueRet += lowest_larger->m_value;
} else {
for (unsigned int i = 0; i < applicable_groups.size(); i++) {
if (vfBest[i]) {
util::insert(setCoinsRet, applicable_groups[i].m_outputs);
nValueRet += applicable_groups[i].m_value;
}
}
if (LogAcceptCategory(BCLog::SELECTCOINS)) {
std::string log_message{"Coin selection best subset: "};
for (unsigned int i = 0; i < applicable_groups.size(); i++) {
if (vfBest[i]) {
log_message += strprintf("%s ", FormatMoney(applicable_groups[i].m_value));
}
}
LogPrint(BCLog::SELECTCOINS, "%stotal %s\n", log_message, FormatMoney(nBest));
}
}
return true;
*/
}