数字相加情况。

網中人

原帖由 "網中人" 发表：
嗯, 有時間我再來想想好了...
看來可能要先 sort 一下,
也可先行將超出最大值的剔除掉,
然後先抓頭抓尾來相加一下, 若不足, 再多抓下一個最小值, 這樣會比較容易些...

try 了一下, 覺得上面的方法也不是很好...

我倒想到用之前的 script 抓出 unused numbers 之後,
再"塞"回給尚可"吃"得進的算式去.
只是, 還沒時間來寫就是了....

zhkun

网中人，谢谢，不错我觉得有意思，才说出来的，不料大家都比较积极。

lightspeed

# cat ./data

32
53
12
150
97
45
24
100
145
1
2
170
3
4


# cat  ./a

#!/bin/ksh

max=150
min=100
initlist=
initsun=
i=0
for j in $(cat $1 | sort -n)
do
        data=$j
        (( i ++ ))
done
num=$(( ${#data

} - 1 ))

getall () {
initlist=$1
list=$1
initsum=$2
sum=$2
i=$3
while [ $i -ge 0 ]
do
        j=${data[$i]}
        if [ "X$list" == "X"  ]
        then
          list=$j
        else
          list=$list" + "$j
        fi
        sum=$(( sum + j ))
        if [ $sum -gt $max ]
        then
                list=$initlist
                sum=$initsum
                (( i -- ))
                continue
        fi
        if [ $sum -le $max -a $sum -ge $min ]
        then
                echo $list" = "$sum
        fi
        if [ $i -eq 0 ]
        then
                break
        fi

# A subshell must be used in case shell varibles are modified by recursion function. Ooops
# Maybe you can remove it in your platform.

(
        j=0
        k="F"
        while [ $j -lt $i ]
        do
                s=${data[$j]}
                s=$(( s + sum ))
                if [ $s -le $max ]
                then
                        k=$j
                else
                        break
                fi       
                (( j ++ ))
        done
        if [ $k != F ]
        then
                 getall "$list" $sum $k

        fi
)

list=$initlist
sum=$initsum
(( i -- ))
done
}

getall "$initlist" "$initsum" $num



运行：

# a data

150 = 150
145 = 145
145 + 4 = 149
145 + 4 + 1 = 150
145 + 3 = 148
145 + 3 + 2 = 150
145 + 3 + 1 = 149
145 + 2 = 147
145 + 2 + 1 = 148
145 + 1 = 146
100 = 100
100 + 45 = 145
100 + 45 + 4 = 149
100 + 45 + 4 + 1 = 150
100 + 45 + 3 = 148
100 + 45 + 3 + 2 = 150
100 + 45 + 3 + 1 = 149
100 + 45 + 2 = 147
100 + 45 + 2 + 1 = 148
100 + 45 + 1 = 146
100 + 32 = 132
100 + 32 + 12 = 144
100 + 32 + 12 + 4 = 148
100 + 32 + 12 + 4 + 2 = 150
100 + 32 + 12 + 4 + 1 = 149
100 + 32 + 12 + 3 = 147
100 + 32 + 12 + 3 + 2 = 149
100 + 32 + 12 + 3 + 2 + 1 = 150
100 + 32 + 12 + 3 + 1 = 148
100 + 32 + 12 + 2 = 146
100 + 32 + 12 + 2 + 1 = 147
100 + 32 + 12 + 1 = 145
100 + 32 + 4 = 136
100 + 32 + 4 + 3 = 139
100 + 32 + 4 + 3 + 2 = 141
100 + 32 + 4 + 3 + 2 + 1 = 142
100 + 32 + 4 + 3 + 1 = 140
100 + 32 + 4 + 2 = 138
100 + 32 + 4 + 2 + 1 = 139
100 + 32 + 4 + 1 = 137
100 + 32 + 3 = 135
100 + 32 + 3 + 2 = 137
100 + 32 + 3 + 2 + 1 = 138
100 + 32 + 3 + 1 = 136
100 + 32 + 2 = 134
100 + 32 + 2 + 1 = 135
100 + 32 + 1 = 133
100 + 24 = 124
100 + 24 + 12 = 136
100 + 24 + 12 + 4 = 140
100 + 24 + 12 + 4 + 3 = 143
100 + 24 + 12 + 4 + 3 + 2 = 145
100 + 24 + 12 + 4 + 3 + 2 + 1 = 146
100 + 24 + 12 + 4 + 3 + 1 = 144
100 + 24 + 12 + 4 + 2 = 142
100 + 24 + 12 + 4 + 2 + 1 = 143
100 + 24 + 12 + 4 + 1 = 141
100 + 24 + 12 + 3 = 139
100 + 24 + 12 + 3 + 2 = 141
100 + 24 + 12 + 3 + 2 + 1 = 142
100 + 24 + 12 + 3 + 1 = 140
100 + 24 + 12 + 2 = 138
100 + 24 + 12 + 2 + 1 = 139
100 + 24 + 12 + 1 = 137
100 + 24 + 4 = 128
100 + 24 + 4 + 3 = 131
100 + 24 + 4 + 3 + 2 = 133
100 + 24 + 4 + 3 + 2 + 1 = 134
100 + 24 + 4 + 3 + 1 = 132
100 + 24 + 4 + 2 = 130
100 + 24 + 4 + 2 + 1 = 131
100 + 24 + 4 + 1 = 129
100 + 24 + 3 = 127
100 + 24 + 3 + 2 = 129
100 + 24 + 3 + 2 + 1 = 130
100 + 24 + 3 + 1 = 128
100 + 24 + 2 = 126
100 + 24 + 2 + 1 = 127
100 + 24 + 1 = 125
100 + 12 = 112
100 + 12 + 4 = 116
100 + 12 + 4 + 3 = 119
100 + 12 + 4 + 3 + 2 = 121
100 + 12 + 4 + 3 + 2 + 1 = 122
100 + 12 + 4 + 3 + 1 = 120
100 + 12 + 4 + 2 = 118
100 + 12 + 4 + 2 + 1 = 119
100 + 12 + 4 + 1 = 117
100 + 12 + 3 = 115
100 + 12 + 3 + 2 = 117
100 + 12 + 3 + 2 + 1 = 118
100 + 12 + 3 + 1 = 116
100 + 12 + 2 = 114
100 + 12 + 2 + 1 = 115
100 + 12 + 1 = 113
100 + 4 = 104
100 + 4 + 3 = 107
100 + 4 + 3 + 2 = 109
100 + 4 + 3 + 2 + 1 = 110
100 + 4 + 3 + 1 = 108
100 + 4 + 2 = 106
100 + 4 + 2 + 1 = 107
100 + 4 + 1 = 105
100 + 3 = 103
100 + 3 + 2 = 105
100 + 3 + 2 + 1 = 106
100 + 3 + 1 = 104
100 + 2 = 102
100 + 2 + 1 = 103
100 + 1 = 101
97 + 53 = 150
97 + 45 = 142
97 + 45 + 4 = 146
97 + 45 + 4 + 3 = 149
97 + 45 + 4 + 3 + 1 = 150
97 + 45 + 4 + 2 = 148
97 + 45 + 4 + 2 + 1 = 149
97 + 45 + 4 + 1 = 147
97 + 45 + 3 = 145
97 + 45 + 3 + 2 = 147
97 + 45 + 3 + 2 + 1 = 148
97 + 45 + 3 + 1 = 146
97 + 45 + 2 = 144
97 + 45 + 2 + 1 = 145
97 + 45 + 1 = 143
97 + 32 = 129
97 + 32 + 12 = 141
97 + 32 + 12 + 4 = 145
97 + 32 + 12 + 4 + 3 = 148
97 + 32 + 12 + 4 + 3 + 2 = 150
97 + 32 + 12 + 4 + 3 + 1 = 149
97 + 32 + 12 + 4 + 2 = 147
97 + 32 + 12 + 4 + 2 + 1 = 148
97 + 32 + 12 + 4 + 1 = 146
97 + 32 + 12 + 3 = 144
97 + 32 + 12 + 3 + 2 = 146
97 + 32 + 12 + 3 + 2 + 1 = 147
97 + 32 + 12 + 3 + 1 = 145
97 + 32 + 12 + 2 = 143
97 + 32 + 12 + 2 + 1 = 144
97 + 32 + 12 + 1 = 142
97 + 32 + 4 = 133
97 + 32 + 4 + 3 = 136
97 + 32 + 4 + 3 + 2 = 138
97 + 32 + 4 + 3 + 2 + 1 = 139
97 + 32 + 4 + 3 + 1 = 137
97 + 32 + 4 + 2 = 135
97 + 32 + 4 + 2 + 1 = 136
97 + 32 + 4 + 1 = 134
97 + 32 + 3 = 132
97 + 32 + 3 + 2 = 134
97 + 32 + 3 + 2 + 1 = 135
97 + 32 + 3 + 1 = 133
97 + 32 + 2 = 131
97 + 32 + 2 + 1 = 132
97 + 32 + 1 = 130
97 + 24 = 121
97 + 24 + 12 = 133
97 + 24 + 12 + 4 = 137
97 + 24 + 12 + 4 + 3 = 140
97 + 24 + 12 + 4 + 3 + 2 = 142
97 + 24 + 12 + 4 + 3 + 2 + 1 = 143
97 + 24 + 12 + 4 + 3 + 1 = 141
97 + 24 + 12 + 4 + 2 = 139
97 + 24 + 12 + 4 + 2 + 1 = 140
97 + 24 + 12 + 4 + 1 = 138
97 + 24 + 12 + 3 = 136
97 + 24 + 12 + 3 + 2 = 138
97 + 24 + 12 + 3 + 2 + 1 = 139
97 + 24 + 12 + 3 + 1 = 137
97 + 24 + 12 + 2 = 135
97 + 24 + 12 + 2 + 1 = 136
97 + 24 + 12 + 1 = 134
97 + 24 + 4 = 125
97 + 24 + 4 + 3 = 128
97 + 24 + 4 + 3 + 2 = 130
97 + 24 + 4 + 3 + 2 + 1 = 131
97 + 24 + 4 + 3 + 1 = 129
97 + 24 + 4 + 2 = 127
97 + 24 + 4 + 2 + 1 = 128
97 + 24 + 4 + 1 = 126
97 + 24 + 3 = 124
97 + 24 + 3 + 2 = 126
97 + 24 + 3 + 2 + 1 = 127
97 + 24 + 3 + 1 = 125
97 + 24 + 2 = 123
97 + 24 + 2 + 1 = 124
97 + 24 + 1 = 122
97 + 12 = 109
97 + 12 + 4 = 113
97 + 12 + 4 + 3 = 116
97 + 12 + 4 + 3 + 2 = 118
97 + 12 + 4 + 3 + 2 + 1 = 119
97 + 12 + 4 + 3 + 1 = 117
97 + 12 + 4 + 2 = 115
97 + 12 + 4 + 2 + 1 = 116
97 + 12 + 4 + 1 = 114
97 + 12 + 3 = 112
97 + 12 + 3 + 2 = 114
97 + 12 + 3 + 2 + 1 = 115
97 + 12 + 3 + 1 = 113
97 + 12 + 2 = 111
97 + 12 + 2 + 1 = 112
97 + 12 + 1 = 110
97 + 4 = 101
97 + 4 + 3 = 104
97 + 4 + 3 + 2 = 106
97 + 4 + 3 + 2 + 1 = 107
97 + 4 + 3 + 1 = 105
97 + 4 + 2 = 103
97 + 4 + 2 + 1 = 104
97 + 4 + 1 = 102
97 + 3 = 100
97 + 3 + 2 = 102
97 + 3 + 2 + 1 = 103
97 + 3 + 1 = 101
97 + 2 + 1 = 100
53 + 45 + 32 = 130
53 + 45 + 32 + 12 = 142
53 + 45 + 32 + 12 + 4 = 146
53 + 45 + 32 + 12 + 4 + 3 = 149
53 + 45 + 32 + 12 + 4 + 3 + 1 = 150
53 + 45 + 32 + 12 + 4 + 2 = 148
53 + 45 + 32 + 12 + 4 + 2 + 1 = 149
53 + 45 + 32 + 12 + 4 + 1 = 147
53 + 45 + 32 + 12 + 3 = 145
53 + 45 + 32 + 12 + 3 + 2 = 147
53 + 45 + 32 + 12 + 3 + 2 + 1 = 148
53 + 45 + 32 + 12 + 3 + 1 = 146
53 + 45 + 32 + 12 + 2 = 144
53 + 45 + 32 + 12 + 2 + 1 = 145
53 + 45 + 32 + 12 + 1 = 143
53 + 45 + 32 + 4 = 134
53 + 45 + 32 + 4 + 3 = 137
53 + 45 + 32 + 4 + 3 + 2 = 139
53 + 45 + 32 + 4 + 3 + 2 + 1 = 140
53 + 45 + 32 + 4 + 3 + 1 = 138
53 + 45 + 32 + 4 + 2 = 136
53 + 45 + 32 + 4 + 2 + 1 = 137
53 + 45 + 32 + 4 + 1 = 135
53 + 45 + 32 + 3 = 133
53 + 45 + 32 + 3 + 2 = 135
53 + 45 + 32 + 3 + 2 + 1 = 136
53 + 45 + 32 + 3 + 1 = 134
53 + 45 + 32 + 2 = 132
53 + 45 + 32 + 2 + 1 = 133
53 + 45 + 32 + 1 = 131
53 + 45 + 24 = 122
53 + 45 + 24 + 12 = 134
53 + 45 + 24 + 12 + 4 = 138
53 + 45 + 24 + 12 + 4 + 3 = 141
53 + 45 + 24 + 12 + 4 + 3 + 2 = 143
53 + 45 + 24 + 12 + 4 + 3 + 2 + 1 = 144
53 + 45 + 24 + 12 + 4 + 3 + 1 = 142
53 + 45 + 24 + 12 + 4 + 2 = 140
53 + 45 + 24 + 12 + 4 + 2 + 1 = 141
53 + 45 + 24 + 12 + 4 + 1 = 139
53 + 45 + 24 + 12 + 3 = 137
53 + 45 + 24 + 12 + 3 + 2 = 139
53 + 45 + 24 + 12 + 3 + 2 + 1 = 140
53 + 45 + 24 + 12 + 3 + 1 = 138
53 + 45 + 24 + 12 + 2 = 136
53 + 45 + 24 + 12 + 2 + 1 = 137
53 + 45 + 24 + 12 + 1 = 135
53 + 45 + 24 + 4 = 126
53 + 45 + 24 + 4 + 3 = 129
53 + 45 + 24 + 4 + 3 + 2 = 131
53 + 45 + 24 + 4 + 3 + 2 + 1 = 132
53 + 45 + 24 + 4 + 3 + 1 = 130
53 + 45 + 24 + 4 + 2 = 128
53 + 45 + 24 + 4 + 2 + 1 = 129
53 + 45 + 24 + 4 + 1 = 127
53 + 45 + 24 + 3 = 125
53 + 45 + 24 + 3 + 2 = 127
53 + 45 + 24 + 3 + 2 + 1 = 128
53 + 45 + 24 + 3 + 1 = 126
53 + 45 + 24 + 2 = 124
53 + 45 + 24 + 2 + 1 = 125
53 + 45 + 24 + 1 = 123
53 + 45 + 12 = 110
53 + 45 + 12 + 4 = 114
53 + 45 + 12 + 4 + 3 = 117
53 + 45 + 12 + 4 + 3 + 2 = 119
53 + 45 + 12 + 4 + 3 + 2 + 1 = 120
53 + 45 + 12 + 4 + 3 + 1 = 118
53 + 45 + 12 + 4 + 2 = 116
53 + 45 + 12 + 4 + 2 + 1 = 117
53 + 45 + 12 + 4 + 1 = 115
53 + 45 + 12 + 3 = 113
53 + 45 + 12 + 3 + 2 = 115
53 + 45 + 12 + 3 + 2 + 1 = 116
53 + 45 + 12 + 3 + 1 = 114
53 + 45 + 12 + 2 = 112
53 + 45 + 12 + 2 + 1 = 113
53 + 45 + 12 + 1 = 111
53 + 45 + 4 = 102
53 + 45 + 4 + 3 = 105
53 + 45 + 4 + 3 + 2 = 107
53 + 45 + 4 + 3 + 2 + 1 = 108
53 + 45 + 4 + 3 + 1 = 106
53 + 45 + 4 + 2 = 104
53 + 45 + 4 + 2 + 1 = 105
53 + 45 + 4 + 1 = 103
53 + 45 + 3 = 101
53 + 45 + 3 + 2 = 103
53 + 45 + 3 + 2 + 1 = 104
53 + 45 + 3 + 1 = 102
53 + 45 + 2 = 100
53 + 45 + 2 + 1 = 101
53 + 32 + 24 = 109
53 + 32 + 24 + 12 = 121
53 + 32 + 24 + 12 + 4 = 125
53 + 32 + 24 + 12 + 4 + 3 = 128
53 + 32 + 24 + 12 + 4 + 3 + 2 = 130
53 + 32 + 24 + 12 + 4 + 3 + 2 + 1 = 131
53 + 32 + 24 + 12 + 4 + 3 + 1 = 129
53 + 32 + 24 + 12 + 4 + 2 = 127
53 + 32 + 24 + 12 + 4 + 2 + 1 = 128
53 + 32 + 24 + 12 + 4 + 1 = 126
53 + 32 + 24 + 12 + 3 = 124
53 + 32 + 24 + 12 + 3 + 2 = 126
53 + 32 + 24 + 12 + 3 + 2 + 1 = 127
53 + 32 + 24 + 12 + 3 + 1 = 125
53 + 32 + 24 + 12 + 2 = 123
53 + 32 + 24 + 12 + 2 + 1 = 124
53 + 32 + 24 + 12 + 1 = 122
53 + 32 + 24 + 4 = 113
53 + 32 + 24 + 4 + 3 = 116
53 + 32 + 24 + 4 + 3 + 2 = 118
53 + 32 + 24 + 4 + 3 + 2 + 1 = 119
53 + 32 + 24 + 4 + 3 + 1 = 117
53 + 32 + 24 + 4 + 2 = 115
53 + 32 + 24 + 4 + 2 + 1 = 116
53 + 32 + 24 + 4 + 1 = 114
53 + 32 + 24 + 3 = 112
53 + 32 + 24 + 3 + 2 = 114
53 + 32 + 24 + 3 + 2 + 1 = 115
53 + 32 + 24 + 3 + 1 = 113
53 + 32 + 24 + 2 = 111
53 + 32 + 24 + 2 + 1 = 112
53 + 32 + 24 + 1 = 110
53 + 32 + 12 + 4 = 101
53 + 32 + 12 + 4 + 3 = 104
53 + 32 + 12 + 4 + 3 + 2 = 106
53 + 32 + 12 + 4 + 3 + 2 + 1 = 107
53 + 32 + 12 + 4 + 3 + 1 = 105
53 + 32 + 12 + 4 + 2 = 103
53 + 32 + 12 + 4 + 2 + 1 = 104
53 + 32 + 12 + 4 + 1 = 102
53 + 32 + 12 + 3 = 100
53 + 32 + 12 + 3 + 2 = 102
53 + 32 + 12 + 3 + 2 + 1 = 103
53 + 32 + 12 + 3 + 1 = 101
53 + 32 + 12 + 2 + 1 = 100
45 + 32 + 24 = 101
45 + 32 + 24 + 12 = 113
45 + 32 + 24 + 12 + 4 = 117
45 + 32 + 24 + 12 + 4 + 3 = 120
45 + 32 + 24 + 12 + 4 + 3 + 2 = 122
45 + 32 + 24 + 12 + 4 + 3 + 2 + 1 = 123
45 + 32 + 24 + 12 + 4 + 3 + 1 = 121
45 + 32 + 24 + 12 + 4 + 2 = 119
45 + 32 + 24 + 12 + 4 + 2 + 1 = 120
45 + 32 + 24 + 12 + 4 + 1 = 118
45 + 32 + 24 + 12 + 3 = 116
45 + 32 + 24 + 12 + 3 + 2 = 118
45 + 32 + 24 + 12 + 3 + 2 + 1 = 119
45 + 32 + 24 + 12 + 3 + 1 = 117
45 + 32 + 24 + 12 + 2 = 115
45 + 32 + 24 + 12 + 2 + 1 = 116
45 + 32 + 24 + 12 + 1 = 114
45 + 32 + 24 + 4 = 105
45 + 32 + 24 + 4 + 3 = 108
45 + 32 + 24 + 4 + 3 + 2 = 110
45 + 32 + 24 + 4 + 3 + 2 + 1 = 111
45 + 32 + 24 + 4 + 3 + 1 = 109
45 + 32 + 24 + 4 + 2 = 107
45 + 32 + 24 + 4 + 2 + 1 = 108
45 + 32 + 24 + 4 + 1 = 106
45 + 32 + 24 + 3 = 104
45 + 32 + 24 + 3 + 2 = 106
45 + 32 + 24 + 3 + 2 + 1 = 107
45 + 32 + 24 + 3 + 1 = 105
45 + 32 + 24 + 2 = 103
45 + 32 + 24 + 2 + 1 = 104
45 + 32 + 24 + 1 = 102

zhkun

good！very，good！！能从中选出最优嘛？

bjgirl

[quote]原帖由 "zhkun"]good！very，good！！能从中选出最优嘛？[/quote 发表：

你自己没有写吗?!

網中人

嗯, 若將條件設為: 每個數字只能用一次呢? (不能重複, 且全要用光.)

沒事, 純好玩, 當練習吧...  ^_^

lightspeed

如果最优条件像楼主所示，是最少相加项，可以这样：

# a data | awk '{print NF " "$0}' ddd|sort -n|awk  '{if (NR == 1) x=$1 + 1; if (NF == x) { $1="";  print $0} }'

100 = 100
145 = 145
150 = 150

如果最优条件像 netman 所言, 也不算难. 但我怀疑是否能数学上能证明对
任何数据文件, 所选
答案正好包含所有数字而没有任何重复.

换句话说, 有可能无解.

xchen301

这类问题，用递归最快最好了，我试一下function来

lightspeed

不好意思, 我上面有笔误,  应去掉 ddd.

另外, 我已找到反例,  netman 的规则无解.  如数据文件为:

98
99
3

则共两个式子满足条件:

98 + 3 = 101
99 + 3 = 102

要想包含所有数字, 则 3 必重复.

zhkun

bjgirl真的不好意思，我对这个问题想了好久了，只是无下手，所有拿来供大家解一解。不过我感觉lightspeed写的有点意思。
条件嘛是在最优最少的加式中，每个数字当然是只使用一次了。