Bash从结果中获取多个数字

Question

我有这些变量也许这可以直到100（最少两个变量）（最大+50）

1=10
2=21
3=44
4=36
...

并且需要找到哪些变量总和到57在这种情况下是变量4 + 2.或者结果可能是90，这种情况是1 + 3 + 4。

我认为需要一些随机代码，也许有些像这样。

#!/bin/bash
array[0]=10
array[1]=21
array[2]=44
array[3]=36
Next add random until this fits to result 

但是，如果我有100个变量并且需要找到结果是否可能？我读了一些随机化的链接，但我从来没有见过这样的东西。

Answer 1

这个递归Bash函数尝试使用暴力查找和打印总和，检查所有可能的总和，方法：

function print_sums
{
    local -r target=$1              # Number for which sums are to be found
    local -r pre_sum=$2             # Sum built up for an outer target
    local -r values=( "${@:3}" )    # Values available to use in sums

    if (( target == 0 )) ; then
        printf '%s\n' "$pre_sum"
    elif (( ${#values[*]} == 0 )) ; then
        :
    else
        # Print any sums that include the first in the list of values
        local first_value=${values[0]}
        if (( first_value <= target )) ; then
            local new_pre_sum
            [[ -z $pre_sum ]]   && new_pre_sum=$first_value \
                                || new_pre_sum="$pre_sum+$first_value"
            local new_target=$((target - first_value))
            print_sums "$new_target" "$new_pre_sum" "${values[@]:1}"
        fi

        # Print any sums that don't include the first in the list of values
        print_sums "$target" "$pre_sum" "${values[@]:1}"
    fi

    return 0
}

示例用法，包含要在sums中使用的可能值的扩展列表：

values=(10 21 44 36 85 61 69 81 76 39 95 22 30 4 29 47 80 18 40 44 )
print_sums 90 '' "${values[@]}"

这打印：

10+21+30+29
10+44+36
10+36+22+4+18
10+36+4+40
10+36+44
10+76+4
10+22+18+40
10+4+29+47
10+80
21+36+4+29
21+69
21+39+30
21+22+29+18
21+22+47
21+4+47+18
21+29+40
61+29
39+22+29
39+4+29+18
39+4+47

在旧的Linux机器上执行此操作只需不到一秒钟。然而，指数爆炸（每个值列表的加法使得要尝试的总和的潜在数量加倍）意味着它对于显着更大数量的值而言不是实际的解决方案。我没有试过50，但除非目标值很小，否则它没有希望，所以你得到了很多早期的回报。

问题要求打印总和中的值的索引，而不是值本身。这可以通过对代码的微小修改来完成（对任何感兴趣的人来说都是一个练习！）。