UTXO选择策略

Question

我需要在选择 UTXO 时应用特定的策略。该策略应尽可能减少 utxo 的使用。应该设置此策略的边界，理想情况下，应优先考虑较少数量的 utxo，直到 10 倍比率。

为了使问题更简单，我们假设有一个整数列表：= []int{}，我需要找到元素'target'，其中：list[index] = target，如果这样的元素不存在，那么我需要从 slice 中找到大于 target 但需要 <= target*10 的第一个元素

如果我找不到这样的元素，那么我需要找到两个元素 x，y 其中：x + y = target，如果这样的元素不存在，我需要从 slice 中找到大于 target 但需要的前两个元素<= 目标*10

如果我无法找到这样的元素，那么我需要找到三个元素 x、y、z 其中：x + y + z = 目标，如果这样的元素不存在，我需要从切片中找到大于目标的前三个元素但需要 <= target*10

如果我找不到这样的三个元素，我需要找到四个、五个……直到 len(list)。

示例 1：

target = 6

list := []int {1,2, 6, 10}

result = list[2] = 6

示例 2：

target = 6

list := []int {1,2, 3, 10}

result = list[3] = 10

示例 3：

target = 6

list := []int {1,2, 3, 10}

result = list[3] = 10

示例 4：

target = 6

list := []int {1,3, 3, 61}

result = list[1]  + list[2]= 6

请参阅下面的测试用例，我需要通过递归或以某种方式改进以获得通用解决方案：

func Test_SelectUtxo(t *testing.T){

    x := 6

    list := []int{1, 2, 3, 64, 65, 62, 62, 62, 61, 59}

    

    fmt.Println("ONE = x")

    for i := 0; i < len(list) - 1; i ++ {

        if list[i] == x {

            fmt.Println(i)

            break

        }

    }

    fmt.Println("ONE <= x*10")

    for i := 0; i < len(list); i ++ {

        if list[i] > x {

            if list[i] <= x*10 && list[i] > x {

                fmt.Println(list[i])

                break

            }

        }

    }

    fmt.Println("TWO = x")

    out:

    for i := 0; i < len(list) - 1; i ++ {

        for j:=i + 1; j < len(list); j ++ {

            if list[i] + list[j] == x {

                fmt.Println(i)

                fmt.Println(j)

                break out

            }

        }

    }

    fmt.Println()

    fmt.Println("TWO <= x*10")

    out1:

    for i := 0; i < len(list) - 1; i ++ {

        for j:=i + 1; j < len(list); j ++ {

            if list[i] + list[j] <= x*10 && list[i] + list[j] > x {

                fmt.Println(i)

                fmt.Println(j)

                break out1

            }

        }

    }

Answer 1

一种解决方案：放size = 1使用递归（函数名称=&nbsp;getCombination在下面的代码片段中）来获取size输入数组中元素的所有组合。检查每个组合是否满足0 -> i的要求，如果是，则返回（完成）如果没有任何组合匹配，则size++，然后转到步骤 2。片段：import (&nbsp; "fmt")var combination = []int{}func GetCombination(src []int,size int, offset int) [][]int { // get all combinations for **size** elements in the elements of src array&nbsp; result := [][]int{}&nbsp; if size == 0 {&nbsp; &nbsp; temp := make([]int, len(combination))&nbsp; &nbsp; copy(temp, combination)&nbsp; &nbsp; return append(result, temp)&nbsp; }&nbsp; for i:=offset; i<=len(src) - size; i++ {&nbsp; &nbsp; combination = append(combination, src[i])&nbsp; &nbsp; temp := GetCombination(src, size-1, i+1)&nbsp; &nbsp; result = append(result, temp...)&nbsp; &nbsp; combination = combination[:len(combination)-1]&nbsp; }&nbsp; return result[:]}func sum(items []int) int {&nbsp; total := 0&nbsp; for _, v := range items {&nbsp; &nbsp; total += v&nbsp; }&nbsp; return total}func GetBestPair(items []int, target int) []int {&nbsp; &nbsp; for i := 1; i < len(items)+1; i++ {&nbsp; &nbsp; &nbsp; &nbsp; result := GetCombination(items, i, 0) // get all possible combinations for 1 -> len(items) elements of Array=items&nbsp; &nbsp; &nbsp; &nbsp; // fmt.Println("Combinations for ", i, " elements:", result)&nbsp; &nbsp; &nbsp; &nbsp; for j := 0; j < len(result); j++ {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; total := sum(result[j])&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if total < target {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; continue&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if total == target {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return result[j]&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if total < target*10 {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return result[j]&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; return []int{}}func main () {&nbsp; fmt.Println("Result", GetBestPair([]int{1, 3, 3, 61}, 6))}上述测试用例的输出Combinations for&nbsp; 1&nbsp; elements: [[1] [3] [3] [61]]Combinations for&nbsp; 2&nbsp; elements: [[1 3] [1 3] [1 61] [3 3] [3 61] [3 61]]Result: [3 3]