题目描述
给定数字5、-5，7，-7，12，-12，每个数字个数无限多，从中选择尽量少的数字，使它们的和为N。
分析
因为对称性，只需要考虑N>0的情况。
因为存在一对互质的正整数（比如5和7），所以总是存在整数x,y使5x+7y=1，只要能够产生1，就一定能够产生任意正整数。因此问题一定有解。
方法一：打表法
自下而上的更新
缺点是比较暴力，占用空间比较大
a = [5, 7, 12, -5, -7, -12]
b = dict()
for i in a:
b[i] = 1
while 2000 not in b:
c = dict()
for i in b:
for j in a:
k = i + j
if k not in b:
c[k] = b[i] + 1
elif b[i] + 1 < b[k]:
b[k] = b[i] + 1
if len(c) == 0:
break
else:
for i in c:
b[i] = c[i]
ans = sorted(list(b.items()))
ans = [i for i in ans if i[0] >= 0]
with open("test.txt", "w") as f:
for i in ans:
f.write("%d %d
" % (i[0], i[1]))
方法二：循环法
最终答案只有两种选择：
5，-7，12
-5，7，12
其余选择必然不是最优解：选了+5就不能选择-5，选了5和7，就不能选-12（抵消了），5、7同时选必然不如选择一个12。
并且5的个数不会超过7，7的个数不会超过12，否则的话，必然不是最优解。
对于给定的正负数数组a，首先对a进行从小到大排序，a[0]的个数不能超过a[1],a[1]的个数不能超过a[2],a[2]的个数不能超过a[3]......
a = [5, 7, 12, -5, -7, -12]
def f(m, x):
ans = 0xfffffff
for i in range(12):
for j in range(12):
left = x - m[0] * i - m[1] * j
if left % m[2] == 0:
ans = min(ans, i + j + abs(left // m[2]))
return ans
def solve(x):
return min(f([5, -7, 12], x), f([-5, 7, 12], x))
def output():
with open("f1.txt", 'w') as file:
for i in range(500):
file.write("%d %d
" % (i, solve(i)))
output()
方法三：方法一和方法二的综合
对于5，7，12三个数字，5的个数肯定不会超过7，7的个数肯定不会超过12。
又因为只有5，-7，12和-7，5，12两种组合，所以有77+30=107
只需要打表出0~107，然后其余部分用12填充即可。
a = [5, 7, 12, -5, -7, -12]
b = dict()
for i in a:
b[i] = 1
limit=43
while limit*3 not in b:
c = dict()
for i in b:
for j in a:
k = i + j
if k not in b:
c[k] = b[i] + 1
elif b[i] + 1 < b[k]:
b[k] = b[i] + 1
if len(c) == 0:
break
else:
for i in c:
b[i] = c[i]
def solve(x):
if x <= limit:
return b[x]
cnt = x // 12
ans = 0xffffff
while x - cnt * 12 < limit:
ans = min(ans, cnt + b[x - cnt * 12])
cnt -= 1
return ans
经过测试，这个问题中的limit至少为43，这是为什么呢？
更一般的提法
给定正整数数组a[N]，从而确定了+a[0],-a[0],+a[1],-a[1]......共2N个整数，从中选择尽量少的数字，使得它们的和为M。
只需打表处理0~a[0]*a[1]+a[1]*a[2]+a[2]*a[3]+a[3]*a[4]范围内的结果，其余部分必定以最大值a[N-1]填充。