编程练习（一）201301 JAVA题目0-1级

编写一个函数，传入一个int型数组，返回该数组能否分成两组，使得两组中各元素加起来的和相等，并且，所有5的倍数必须在其中一个组中，所有3的倍数在另一个组中（不包括5的倍数），能满足以上条件，返回true；不满足时返回false。

方法一：暴力求解

while 1:
    try:
        n = input()
        l = input().split() # 列表
        sum1 = sum2 = 0
        ll = [] # 保存 3，5 之外的数
        for i in l:
            if int(i) % 5 == 0:
                sum1 += int(i)
            elif int(i) % 3 == 0:
                sum2 += int(i)
            else:
                ll.append(int(i))
        d_value = abs(sum1 - sum2) # 2*x + d_value = sum(ll) ===> d_value = sum(ll) - 2 * x
        if not ll and d_value == 0:
            print (‘true‘)
        elif not ll and d_value != 0:
            print (‘false‘)
        else: # 存在差值，并且有剩余数字
            s = set()
            for x in ll:
                tmp = list(s)
                for y in tmp:
                    s.add(x + y)
                s.add(x)
            for may_value in s:
                if d_value == abs((sum(ll) - may_value) - may_value):
                    print (‘true‘)
                    break
            else:
                print (‘false‘)
    except:
        break

解析：首先得到 sum1, sum2，剩下的数字组成的列表ll, 以及二者的差值。如果成立，则存在x使得： 2*x + d_value = sum(ll)。即
d_value = sum(ll) - 2 * x。最朴素的方法，找到列表ll中所有数字和所有可能的值，然后代入比较。
所以问题转换为如何求一个数组中所有数字求和得到的值。

list_ = [1,2,3,4,5,6,7,5,3,2,1,5,99]
s = set()
for x in list_:
    tmp = list(s)
    for y in tmp:
        s.add(x +y)
    s.add(x)
print(s)

s 的值 {x1,x1+x2,x2,x1+x3,x1+x2+x3,x2+x3,x3......}
方法二：递归

def search(ll, target):
    if target == 0:
        return True
    if not ll:
        return False
    return search(ll[1:],target) or search(ll[1:],target - ll[0])
 
 
while True:
    try:
        m,ls = int(input()),list(map(int, input().split()))
  
        ls1 = []
        ls2 = []
        ls3 = []
 
 
        for i in ls:
            if i%5 == 0:
                ls1.append(i)
            elif i%3 ==0:
                ls2.append(i)
            else:
                ls3.append(i)
        t = abs(sum(ls1)-sum(ls2))
        d = sum(ls3) - t
        if d%2 != 0:
            print(‘false‘)
        else:
            if search(ls3,d/2):
                print(‘true‘)
            else:
                print(‘false‘)
    except:
        break

解析：search()递归函数的理解，未完待续。

编程练习（一）201301 JAVA题目0-1级

原文：https://www.cnblogs.com/leimu/p/13432135.html