rust_coinselect/algorithms/
knapsack.rs

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

rust_coinselect/algorithms/
knapsack.rs
