rust_coinselect/algorithms/
knapsack.rs

1use crate::{
2    types::{
3        CoinSelectionOpt, EffectiveValue, OutputGroup, SelectionError, SelectionOutput, WasteMetric,
4    },
5    utils::{calculate_fee, calculate_waste, effective_value},
6};
7use rand::{thread_rng, Rng};
8use std::collections::HashSet;
9pub fn select_coin_knapsack(
10    inputs: &[OutputGroup],
11    options: &CoinSelectionOpt,
12) -> Result<SelectionOutput, SelectionError> {
13    // Calculate base fees with no inputs
14    let base_fees = calculate_fee(options.base_weight, options.target_feerate).unwrap_or_default();
15    let adjusted_target =
16        options.target_value + options.min_change_value + base_fees.max(options.min_absolute_fee);
17
18    let mut smaller_coins = inputs
19        .iter()
20        .enumerate()
21        .filter(|&(_, output_group)| output_group.value < adjusted_target)
22        .map(|(index, output_group)| {
23            (
24                index,
25                output_group.value,
26                output_group.weight,
27                effective_value(output_group, options.target_feerate),
28            )
29        })
30        .collect::<Vec<_>>();
31
32    // Sort by effective value descending
33    smaller_coins.sort_by(|(_, _, _, a), (_, _, _, b)| b.unwrap_or(0).cmp(&a.unwrap_or(0)));
34
35    let smaller_coins: Vec<_> = smaller_coins
36        .into_iter()
37        .filter_map(|(index, value, weight, eff_value)| {
38            eff_value.ok().map(|v| (index, value, weight, v))
39        })
40        .collect();
41
42    knap_sack(&smaller_coins, adjusted_target, options)
43}
44
45fn knap_sack(
46    smaller_coins: &[(usize, u64, u64, EffectiveValue)],
47    adjusted_target: u64,
48    options: &CoinSelectionOpt,
49) -> Result<SelectionOutput, SelectionError> {
50    let mut selected_inputs: HashSet<usize> = HashSet::new();
51    let mut accumulated_value: u64 = 0;
52    let mut accumulated_weight: u64 = 0;
53    let mut best_set: HashSet<usize> = HashSet::new();
54    let mut best_set_value: u64 = u64::MAX;
55    let mut best_set_weight: u64 = 0;
56    let mut rng = thread_rng();
57
58    for _ in 1..=1000 {
59        for pass in 1..=2 {
60            for &(index, value, weight, _eff_value) in smaller_coins {
61                let toss_result: bool = rng.gen_bool(0.5);
62                if (pass == 2 && !selected_inputs.contains(&index)) || (pass == 1 && toss_result) {
63                    selected_inputs.insert(index);
64                    accumulated_value += value;
65                    accumulated_weight += weight;
66
67                    // Calculate current fees and required value
68                    let estimated_fees = calculate_fee(accumulated_weight, options.target_feerate)?;
69                    let required_value = adjusted_target + estimated_fees;
70
71                    if accumulated_value == required_value {
72                        let waste = calculate_waste(
73                            options,
74                            accumulated_value,
75                            accumulated_weight,
76                            estimated_fees,
77                        );
78                        let index_vector: Vec<usize> = selected_inputs.into_iter().collect();
79                        return Ok(SelectionOutput {
80                            selected_inputs: index_vector,
81                            waste: WasteMetric(waste),
82                        });
83                    } else if accumulated_value >= required_value {
84                        if accumulated_value < best_set_value {
85                            best_set_value = accumulated_value;
86                            best_set_weight = accumulated_weight;
87                            best_set.clone_from(&selected_inputs);
88                        }
89                        selected_inputs.remove(&index);
90                        accumulated_value -= value;
91                        accumulated_weight -= weight;
92                    }
93                }
94            }
95        }
96        accumulated_value = 0;
97        accumulated_weight = 0;
98        selected_inputs.clear();
99    }
100
101    if best_set_value == u64::MAX {
102        Err(SelectionError::NoSolutionFound)
103    } else {
104        let estimated_fees = calculate_fee(best_set_weight, options.target_feerate)?;
105        let waste = calculate_waste(options, best_set_value, best_set_weight, estimated_fees);
106        let index_vector: Vec<usize> = best_set.into_iter().collect();
107        Ok(SelectionOutput {
108            selected_inputs: index_vector,
109            waste: WasteMetric(waste),
110        })
111    }
112}
113
114#[cfg(test)]
115mod test {
116
117    use crate::{
118        algorithms::knapsack::select_coin_knapsack,
119        types::{CoinSelectionOpt, ExcessStrategy, OutputGroup, SelectionError},
120        utils::calculate_fee,
121    };
122
123    const CENT: f64 = 1000000.0;
124    const COIN: f64 = 100000000.0;
125    const RUN_TESTS: u32 = 100;
126    const RUN_TESTS_SLIM: u32 = 10;
127
128    fn knapsack_setup_options(adjusted_target: u64, target_feerate: f32) -> CoinSelectionOpt {
129        let min_change_value = 500;
130        let base_weight = 10;
131        let target_value = adjusted_target
132            - min_change_value
133            - calculate_fee(base_weight, target_feerate).unwrap_or_default();
134        CoinSelectionOpt {
135            target_value,
136            target_feerate, // Simplified feerate
137            long_term_feerate: Some(0.4),
138            min_absolute_fee: 0,
139            base_weight,
140            change_weight: 50,
141            change_cost: 10,
142            avg_input_weight: 20,
143            avg_output_weight: 10,
144            min_change_value,
145            excess_strategy: ExcessStrategy::ToChange,
146        }
147    }
148
149    fn knapsack_setup_output_groups(
150        value: Vec<u64>,
151        weights: Vec<u64>,
152        target_feerate: f32,
153    ) -> Vec<OutputGroup> {
154        let mut inputs: Vec<OutputGroup> = Vec::new();
155        for (i, j) in value.into_iter().zip(weights.into_iter()) {
156            // input value = effective value + fees
157            // Example If we want our input to be equal to 1 CENT while being considered by knapsack(effective value), we have to increase the input by the fees to beginwith
158            let k = i.saturating_add(calculate_fee(j, target_feerate).unwrap_or_default());
159            inputs.push(OutputGroup {
160                value: k,
161                weight: j,
162                input_count: 1,
163                creation_sequence: None,
164            })
165        }
166        inputs
167    }
168
169    fn knapsack_add_to_output_group(
170        inputs: &mut Vec<OutputGroup>,
171        value: Vec<u64>,
172        weights: Vec<u64>,
173        target_feerate: f32,
174    ) {
175        for (i, j) in value.into_iter().zip(weights.into_iter()) {
176            // input value = effective value + fees
177            // Example If we want our input to be equal to 1 CENT while being considered by knapsack(effective value), we have to increase the input by the fees to beginwith
178            let k = i.saturating_add(calculate_fee(j, target_feerate).unwrap_or_default());
179            inputs.push(OutputGroup {
180                value: k,
181                weight: j,
182                input_count: 1,
183                creation_sequence: None,
184            })
185        }
186    }
187
188    fn knapsack_test_vectors() {
189        let mut inputs_verify: Vec<usize> = Vec::new();
190        for _ in 0..RUN_TESTS {
191            // Test if Knapsack retruns an Error
192            let mut inputs: Vec<OutputGroup> = Vec::new();
193            let mut options = knapsack_setup_options(1000, 0.33);
194            let mut result = select_coin_knapsack(&inputs, &options);
195            assert!(matches!(result, Err(SelectionError::NoSolutionFound)));
196
197            // Adding 2 CENT and 1 CENT to the wallet and testing if knapsack can select the two inputs for a 3 CENT Output
198            inputs = knapsack_setup_output_groups(
199                vec![(2.0 * CENT).round() as u64, (1.0 * CENT).round() as u64],
200                vec![130, 100],
201                0.56,
202            );
203            options = knapsack_setup_options((3.0 * CENT).round() as u64, 0.56);
204            if let Ok(result) = select_coin_knapsack(&inputs, &options) {
205                // Checking if knapsack selectes exactly two inputs
206                assert_eq!(result.selected_inputs.len(), 2);
207                // Checking if the selected inputs are 2 and 1 CENTS
208                inputs_verify = vec![0, 1];
209                assert!(inputs_verify
210                    .iter()
211                    .all(|&item| result.selected_inputs.contains(&item)));
212            }
213            inputs_verify.clear();
214            // Adding 20, 10 and 5 CENT to the wallet, totalling 38 CENTS
215            knapsack_add_to_output_group(
216                &mut inputs,
217                vec![
218                    (5.0 * CENT).round() as u64,
219                    (10.0 * CENT).round() as u64,
220                    (20.0 * CENT).round() as u64,
221                ],
222                vec![100, 10, 50],
223                0.56,
224            );
225            // Testing if knapsack can select 4 inputs (2,5,10,20) CENTS to make 37 CENTS
226            options = knapsack_setup_options((37.0 * CENT).round() as u64, 0.56);
227            if let Ok(result) = select_coin_knapsack(&inputs, &options) {
228                // Checking if knapsack selects exactly 4 inputs
229                assert_eq!(result.selected_inputs.len(), 4);
230                // Checking if the selected inputs are 20, 10, 5, 2 CENTS
231                inputs_verify = vec![4, 3, 2, 0];
232                assert!(inputs_verify
233                    .iter()
234                    .all(|&item| result.selected_inputs.contains(&item)));
235            }
236            inputs_verify.clear();
237            // Testing if knapsack can select all the available inputs (2,1,5,10,20) CENTS to make 38 CENTS
238            options = knapsack_setup_options((38.0 * CENT).round() as u64, 0.56);
239            if let Ok(result) = select_coin_knapsack(&inputs, &options) {
240                // Cehcking if knapsack selects exactly 5 inputs
241                assert_eq!(result.selected_inputs.len(), 5);
242                // Cehcking if the selected inputs are 20, 10, 5, 2, 1 CENTS
243                inputs_verify = vec![4, 3, 2, 1, 0];
244                assert!(inputs_verify
245                    .iter()
246                    .all(|&item| result.selected_inputs.contains(&item)));
247            }
248            inputs_verify.clear();
249            // Testing if knapsack can select 3 inputs (5,10,20) CENTS to make 34 CENTS
250            options = knapsack_setup_options((34.0 * CENT).round() as u64, 0.56);
251            if let Ok(result) = select_coin_knapsack(&inputs, &options) {
252                // Checking if knapsack selects exactly 3 inputs
253                assert_eq!(result.selected_inputs.len(), 3);
254                // Cehcking if the selected inputs are 20, 10, 5
255                inputs_verify = vec![4, 3, 2];
256                assert!(inputs_verify
257                    .iter()
258                    .all(|&item| result.selected_inputs.contains(&item)));
259            }
260            inputs_verify.clear();
261            // Testing if knapsack can select 2 inputs (5,2) CENTS to make 7 CENTS
262            options = knapsack_setup_options((7.0 * CENT).round() as u64, 0.56);
263            if let Ok(result) = select_coin_knapsack(&inputs, &options) {
264                // Chekcing if knapsack selects exactly 2 inputs
265                assert_eq!(result.selected_inputs.len(), 2);
266                // Checking if the selected inputs are 5, 2 CENTS
267                inputs_verify = vec![0, 2];
268                assert!(inputs_verify
269                    .iter()
270                    .all(|&item| result.selected_inputs.contains(&item)));
271            }
272            inputs_verify.clear();
273            // Testing if knapsack can select 3 inputs (5,2,1) CENTS to make 8 CENTS
274            options = knapsack_setup_options((8.0 * CENT).round() as u64, 0.56);
275            if let Ok(result) = select_coin_knapsack(&inputs, &options) {
276                // Chekcing if knapsack selects exactly 3 inputs
277                assert_eq!(result.selected_inputs.len(), 3);
278                // Checking if the selected inputs are 5,2,1 CENTS
279                inputs_verify = vec![0, 2, 1];
280                assert!(inputs_verify
281                    .iter()
282                    .all(|&item| result.selected_inputs.contains(&item)));
283            }
284            inputs_verify.clear();
285            // Testing if knapsack can select 1 input (10) CENTS to make 9 CENTS
286            options = knapsack_setup_options((10.0 * CENT).round() as u64, 0.56);
287            if let Ok(result) = select_coin_knapsack(&inputs, &options) {
288                // Chekcing if knapsack selects exactly 1 inputs
289                assert_eq!(result.selected_inputs.len(), 1);
290                // Checking if the selected inputs are 10 CENTS
291                inputs_verify = vec![10];
292                assert!(inputs_verify
293                    .iter()
294                    .all(|&item| result.selected_inputs.contains(&item)));
295            }
296            inputs_verify.clear();
297            // Clearing the input vector
298            inputs.clear();
299            // Adding 30, 20, 8, 7,6 CENT to the wallet, totalling 71 CENTS
300            // Adding 0.001 CENT to the inputs to account for fees
301            inputs = knapsack_setup_output_groups(
302                vec![
303                    (6.0 * CENT).round() as u64,
304                    (7.0 * CENT).round() as u64,
305                    (8.0 * CENT).round() as u64,
306                    (20.0 * CENT).round() as u64,
307                    (30.0 * CENT).round() as u64,
308                ],
309                vec![100, 200, 100, 10, 5],
310                0.77,
311            );
312            // Testing if Knapsack returns an Error while trying to select inputs totalling 72 CENTS
313            options = knapsack_setup_options((72.0 * CENT).round() as u64, 0.77);
314            result = select_coin_knapsack(&inputs, &options);
315            assert!(matches!(result, Err(SelectionError::NoSolutionFound)));
316            // Testing if knapsack can select 3 input (6,7,8) CENTS to make 16 CENTS
317            options = knapsack_setup_options((16.0 * CENT).round() as u64, 0.77);
318            if let Ok(result) = select_coin_knapsack(&inputs, &options) {
319                // Chekcing if knapsack selects exactly 3 inputs
320                assert_eq!(result.selected_inputs.len(), 3);
321                // Checking if the selected inputs are 6,7,8 CENTS
322                inputs_verify = vec![0, 1, 2];
323                assert!(inputs_verify
324                    .iter()
325                    .all(|&item| result.selected_inputs.contains(&item)));
326            }
327            inputs_verify.clear();
328            // Adding 5 CENT to the wallet, totalling 76 CENTS
329            knapsack_add_to_output_group(
330                &mut inputs,
331                vec![(5.0 * CENT).round() as u64],
332                vec![10],
333                0.77,
334            );
335            // Testing if knapsack can select 3 input (5,6,7) CENTS to make 16 CENTS
336            options = knapsack_setup_options((16.0 * CENT).round() as u64, 0.77);
337            if let Ok(result) = select_coin_knapsack(&inputs, &options) {
338                // Chekcing if knapsack selects exactly 3 inputs
339                assert_eq!(result.selected_inputs.len(), 3);
340                // Checking if the selected inputs are 6,7,8 CENTS
341                inputs_verify = vec![0, 1, 5];
342                assert!(inputs_verify
343                    .iter()
344                    .all(|&item| result.selected_inputs.contains(&item)));
345            }
346            inputs_verify.clear();
347
348            // Adding 18 CENT to the wallet, totalling 94 CENTS
349            knapsack_add_to_output_group(
350                &mut inputs,
351                vec![(18.0 * CENT).round() as u64],
352                vec![1],
353                0.77,
354            );
355            // Testing if knapsack can select 2 input (5,6) CENTS to make 11 CENTS
356            options = knapsack_setup_options((11.0 * CENT).round() as u64, 0.77);
357            if let Ok(result) = select_coin_knapsack(&inputs, &options) {
358                // Chekcing if knapsack selects exactly 2 inputs
359                assert_eq!(result.selected_inputs.len(), 2);
360                // Checking if the selected input is 5,6 CENTS
361                inputs_verify = vec![0, 5];
362                assert!(inputs_verify
363                    .iter()
364                    .all(|&item| result.selected_inputs.contains(&item)));
365            }
366            inputs_verify.clear();
367            // Clearing the input vector
368            inputs.clear();
369            // Adding 0.1, 0.2, 0.3, 0.4, 0.5 CENT to the wallet, totalling 1.5 CENTS
370            inputs = knapsack_setup_output_groups(
371                vec![
372                    (0.101 * CENT).round() as u64,
373                    (0.201 * CENT).round() as u64,
374                    (0.301 * CENT).round() as u64,
375                    (0.401 * CENT).round() as u64,
376                    (0.501 * CENT).round() as u64,
377                ],
378                vec![14, 45, 6, 10, 100],
379                0.56,
380            );
381            // Testing if knapsack can select 3 input (0.1, 0.4, 0.5| 0.2, 0.3, 0.5) CENTS to make 1 CENTS
382            options = knapsack_setup_options((1.0 * CENT).round() as u64, 0.56);
383            if let Ok(result) = select_coin_knapsack(&inputs, &options) {
384                // Chekcing if knapsack selects exactly 3 inputs
385                assert_eq!(result.selected_inputs.len(), 3);
386                // Checking if the selected input is 0.1,0.4,0.5 CENTS
387                inputs_verify = vec![0, 3, 4];
388                let valid_inputs_1 = inputs_verify
389                    .iter()
390                    .all(|&item| result.selected_inputs.contains(&item));
391                inputs_verify.clear();
392                inputs_verify = vec![1, 2, 4];
393                let valid_inputs_2 = inputs_verify
394                    .iter()
395                    .all(|&item| result.selected_inputs.contains(&item));
396                assert!(valid_inputs_1 || valid_inputs_2);
397            }
398            inputs_verify.clear();
399            // Mt.Gox Test
400            inputs.clear();
401            // Adding 11, 50,000 COINS to the input
402            inputs = knapsack_setup_output_groups(
403                vec![
404                    (50000.0 * COIN).round() as u64,
405                    (50000.0 * COIN).round() as u64,
406                    (50000.0 * COIN).round() as u64,
407                    (50000.0 * COIN).round() as u64,
408                    (50000.0 * COIN).round() as u64,
409                    (50000.0 * COIN).round() as u64,
410                    (50000.0 * COIN).round() as u64,
411                    (50000.0 * COIN).round() as u64,
412                    (50000.0 * COIN).round() as u64,
413                    (50000.0 * COIN).round() as u64,
414                    (50000.0 * COIN).round() as u64,
415                ],
416                vec![1, 20, 3, 200, 150, 5, 88, 93, 101, 34, 17],
417                0.59,
418            );
419            // Testing if knapsack can select 10 inputs to make 500,000 COINS
420            options = knapsack_setup_options((500000.0 * COIN).round() as u64, 0.59);
421            if let Ok(result) = select_coin_knapsack(&inputs, &options) {
422                // Chekcing if knapsack selects exactly 10 inputs
423                assert_eq!(result.selected_inputs.len(), 10);
424            }
425            // Clearing the input vectors
426            inputs.clear();
427            // Adding 0.4, 0.6, 0.8, 1111 CENTS to the wallet totalling 1112.8 CENTS
428            inputs = knapsack_setup_output_groups(
429                vec![
430                    (0.4 * CENT).round() as u64,
431                    (0.6 * CENT).round() as u64,
432                    (0.8 * CENT).round() as u64,
433                    (1111.0 * CENT).round() as u64,
434                ],
435                vec![14, 45, 6, 10],
436                0.56,
437            );
438            // Testing if knapsack can select 2 input (0.4,0.6) CENTS to make 1 CENTs
439            options = knapsack_setup_options((1.0 * CENT).round() as u64, 0.56);
440            if let Ok(result) = select_coin_knapsack(&inputs, &options) {
441                // Chekcing if knapsack selects exactly 2 inputs
442                assert_eq!(result.selected_inputs.len(), 2);
443                // Checking if the selected input is 0.4,0.6 CENTS
444                inputs_verify = vec![0, 1];
445                assert!(inputs_verify
446                    .iter()
447                    .all(|&item| result.selected_inputs.contains(&item)));
448            }
449            inputs_verify.clear();
450            // Clearing the input vectors
451            inputs.clear();
452            // Adding 0.05, 1, 100 CENTS to the wallet totalling 101.05 CENTS
453            inputs = knapsack_setup_output_groups(
454                vec![
455                    (100.0 * CENT).round() as u64,
456                    (1.0 * CENT).round() as u64,
457                    (0.05 * CENT).round() as u64,
458                ],
459                vec![14, 45, 6],
460                0.56,
461            );
462            // Testing if knapsack can select 2 input (100,1) CENTS to make 100.01 CENTs, therby avoiding creating small change if 100 & 0.05 is chosen
463            options = CoinSelectionOpt {
464                target_value: (100.01 * CENT).round() as u64,
465                target_feerate: 0.56, // Simplified feerate
466                long_term_feerate: Some(0.4),
467                min_absolute_fee: 0,
468                base_weight: 10,
469                change_weight: 50,
470                change_cost: 10,
471                avg_input_weight: 20,
472                avg_output_weight: 10,
473                min_change_value: (0.05 * CENT).round() as u64, // Setting minimum change value = 0.05 CENT. This will make the algorithm to avoid creating small change.
474                excess_strategy: ExcessStrategy::ToChange,
475            };
476            if let Ok(result) = select_coin_knapsack(&inputs, &options) {
477                // Chekcing if knapsack selects exactly 2 inputs
478                assert_eq!(result.selected_inputs.len(), 2);
479                // Checking if the selected input is 0.4,0.6 CENTS
480                inputs_verify = vec![0, 1];
481                assert!(inputs_verify
482                    .iter()
483                    .all(|&item| result.selected_inputs.contains(&item)));
484            }
485            inputs_verify.clear();
486            // Clearing the input vectors
487            inputs.clear();
488        }
489        // Test with multiple inputs
490        let mut inputs: Vec<OutputGroup> = Vec::new();
491        let mut amt = 1500;
492        // Increase the input amoutn startig from 1500 Sats to COIN = 100000000 Sats in multiples of 10
493        while amt < COIN as u64 {
494            inputs.clear();
495            // Declare value and weights vectors
496            let mut input_value: Vec<u64> = Vec::new();
497            let mut input_weight: Vec<u64> = Vec::new();
498            for _ in 0..676 {
499                // Populate the vectors with the same value 'amt' and weight = 23 for 676 times
500                // Using 676 as (old MAX_STANDARD_TX_SIZE = 100000)/(148 bytes per input) = 676
501                input_value.push(amt);
502                input_weight.push(23);
503            }
504            let inputs = knapsack_setup_output_groups(input_value, input_weight, 0.34);
505            // Setting the selection target to 2000 sats
506            let options = knapsack_setup_options(2000, 0.34);
507            // performing the assertion operation 10 times
508            for _ in 0..RUN_TESTS_SLIM {
509                if let Ok(result) = select_coin_knapsack(&inputs, &options) {
510                    if let Some(amt_in_inputs) = inputs.first() {
511                        // Checking if the (input's value) - 2000 is less than CENT
512                        // If so, more than one input is required to meet the selection target of 2000 sats
513                        if amt_in_inputs.value.checked_sub(2000) < Some(CENT as u64) {
514                            // calculating the no.of inputs that will be required to meet the selection target of 2000 sats
515                            let return_size = ((2000.0) / amt as f64).ceil();
516                            assert_eq!(result.selected_inputs.len(), return_size as usize);
517                        } else {
518                            // If (input's value) - 2000 is greater than CENT, then only one input is required to meet the selection target of 2000 sats
519                            assert_eq!(result.selected_inputs.len(), 1);
520                        }
521                    } else {
522                        println!("unable to access 0th element of input vector");
523                    }
524                }
525            }
526            amt *= 10;
527        }
528        inputs.clear();
529        // Testing for Randomness
530        // Declare input value and weights vectors
531        let mut input_value: Vec<u64> = Vec::new();
532        let mut input_weight: Vec<u64> = Vec::new();
533        for _ in 0..=100 {
534            // Populate the vectors with the same value, COIN = 100000000 sats, and weight = 23 for 100 times (to create 100 identical inputs)
535            input_value.push(COIN as u64);
536            input_weight.push(23);
537        }
538        // Setting up inputs
539        let mut inputs = knapsack_setup_output_groups(input_value, input_weight, 0.34);
540        // Setting the selection target to 50*COIN sats
541        let options = knapsack_setup_options((50.0 * COIN).round() as u64, 0.34);
542        let mut selected_input_1: Vec<usize> = Vec::new();
543        let mut selected_input_2: Vec<usize> = Vec::new();
544        for _ in 0..RUN_TESTS {
545            if let Ok(result) = select_coin_knapsack(&inputs, &options) {
546                selected_input_1.clone_from(&result.selected_inputs);
547            }
548            if let Ok(result) = select_coin_knapsack(&inputs, &options) {
549                selected_input_2.clone_from(&result.selected_inputs);
550            }
551            // Checking if the selected inputs, in two consequtive calls of the knapsack function are not the same
552            assert_ne!(selected_input_1, selected_input_2);
553        }
554        selected_input_1.clear();
555        selected_input_2.clear();
556        // Adding 5, 10, 15, 20, 25 CENT to the wallet, Totalling 175,000,000 SATS
557        knapsack_add_to_output_group(
558            &mut inputs,
559            vec![
560                (5.0 * CENT).round() as u64,
561                (10.0 * CENT).round() as u64,
562                (15.0 * CENT).round() as u64,
563                (20.0 * CENT).round() as u64,
564                (25.0 * CENT).round() as u64,
565            ],
566            vec![100, 10, 50, 52, 13],
567            0.34,
568        );
569    }
570
571    #[test]
572    fn test_knapsack() {
573        knapsack_test_vectors();
574    }
575}
rust_coinselect/algorithms/knapsack.rs

rust_coinselect/algorithms/
knapsack.rs
