首页 > 代码库 > 找出给定数组的子数组，该子数组和恰好为给定目标数t----动态规划/递归/搜索(待完成)

找出给定数组的子数组，该子数组和恰好为给定目标数t----动态规划/递归/搜索(待完成)

2024-09-18 18:43:04   215人阅读

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

输入描述：

第一行是数据个数，第二行是输入的数据

输出描述：

返回true或false

输入例子:
4
1 5 -5 1

输出例子:

true
v1=int(raw_input())
v2=raw_input().split(‘ ‘)
v2=map(int,v2)
a=[]
b=[]
c=[]
for i in v2:
    if i%3==0 and i%5!=0:
        a.append(i)
    elif i%5==0:
        b.append(i)
    else:
        c.append(i)
a1=sum(a)
b1=sum(b)
c1=sum(c)
dif=abs(a1-b1)
#x-y=dif
#x+y=c1
x=(dif+c1)%2
y=(c1-dif)%2
if x==0 and y==0:###如果x,y均为0，也就是x1有整数解，才有可能找到满足结果的数组，接下来就是判断，在a中或者b中，能否找到子数组和恰好为x1
    x1=(dif+c1)/2
    c1=sorted(c1)
    ads=0
    lis=[]
    i=0
    while ads<=x1:
        lis.append(c1[i])
        ads+=c1[i]
        i+=1
    print ‘true‘
else:
    print ‘false‘

 

找出给定数组的子数组，该子数组和恰好为给定目标数t----动态规划/递归/搜索(待完成)


联系
我们