ELEMENTS:
| 256 | |
| 257 | // ELEMENTS: |
| 258 | std::optional<SelectionResult> KnapsackSolver(std::vector<OutputGroup>& groups, const CAmountMap& mapTargetValue) |
| 259 | { |
| 260 | SelectionResult result(mapTargetValue); |
| 261 | |
| 262 | std::vector<OutputGroup> inner_groups; |
| 263 | std::set<CInputCoin> setCoinsRet; |
| 264 | CAmount non_policy_effective_value = 0; |
| 265 | |
| 266 | // Perform the standard Knapsack solver for every non-policy asset individually. |
| 267 | for (std::map<CAsset, CAmount>::const_iterator it = mapTargetValue.begin(); it != mapTargetValue.end(); ++it) { |
| 268 | inner_groups.clear(); |
| 269 | |
| 270 | if (it->second == 0) { |
| 271 | continue; |
| 272 | } |
| 273 | if (it->first == ::policyAsset) { |
| 274 | continue; |
| 275 | } |
| 276 | |
| 277 | // We filter the groups on two conditions: |
| 278 | // - only groups that have (exclusively) coins of the asset we're solving for |
| 279 | // - no groups that are already used in the input set |
| 280 | for (const OutputGroup& g : groups) { |
| 281 | bool add = true; |
| 282 | for (const CInputCoin& c : g.m_outputs) { |
| 283 | auto input_set = result.GetInputSet(); |
| 284 | if (input_set.find(c) != input_set.end()) { |
| 285 | add = false; |
| 286 | break; |
| 287 | } |
| 288 | |
| 289 | if (c.asset != it->first) { |
| 290 | add = false; |
| 291 | break; |
| 292 | } |
| 293 | } |
| 294 | |
| 295 | if (add) { |
| 296 | inner_groups.push_back(g); |
| 297 | } |
| 298 | } |
| 299 | |
| 300 | if (inner_groups.size() == 0) { |
| 301 | // No output groups for this asset. |
| 302 | return std::nullopt; |
| 303 | } |
| 304 | |
| 305 | if (auto inner_result = KnapsackSolver(inner_groups, it->second, it->first)) { |
| 306 | auto set = inner_result->GetInputSet(); |
| 307 | for (const CInputCoin& ic : set) { |
| 308 | non_policy_effective_value += ic.effective_value; |
| 309 | } |
| 310 | result.AddInput(inner_result.value()); |
| 311 | } else { |
| 312 | LogPrint(BCLog::SELECTCOINS, "Not enough funds to create target %d for asset %s\n", it->second, it->first.GetHex()); |
| 313 | return std::nullopt; |
| 314 | } |
| 315 | } |