查找最大加权子集，使得子集中的任何两个元素的总和不等于 k

Question

子集的权重是每个键的值的长度。

这是我的尝试：

def nonDivisibleSubset(k, s):
remdict={}
result=[]
for i in range(len(s)):
rem=s[i]%k
if rem not in remdict:
remdict[rem]=[s[i]]
else:
remdict[rem].append(s[i])
b=dict(sorted(remdict.items(), key= lambda x: len(x[1]), reverse=True))

Input: 
k=7
{2: [576, 338, 149, 702, 282, 436], 6: [496, 727, 209], 5: [278, 124], 4: [410, 718], 1: [771, 575]}

从这个字典中，我只想附加键 2,6,4 的值，因为 2+6！=7 和 2+4！=7 和 6+4！=7**

Answer 1

所以首先 - 我们需要找到所有不同的组合，然后从中找到最大值。

这是查找所有不同组合的代码：

def check(d, s, k):
for i in d:
if i + s == k:
return False
return True
for i in s:
temp = [i]
d = s.copy()
d.pop(i)
for j in d:
if check(temp, j, k):
temp.append(j)
temp.sort()
res_lst.append(temp)
unique_data = [list(x) for x in set(tuple(x) for x in res_lst)]

(参考如何查找unique_data：Python：列表列表的唯一性(

要查找最大子集，请执行以下操作：

res = []
res_sum = 0
for l in unique_data:
tmp_sum = 0
for n in l:
tmp_sum += len(s[n])
if tmp_sum > res_sum:
res = l
res_sum = tmp_sum
return res

Answer 2

这个想法是根据它们除以 k 时给出的余数将 s 中的数字分组，并将余数存储为键，并将其频率/计数存储为值。然后在max(key，k-key(之间进行选择，并确保只选择一个如果key==0或key+key=k。可能还有其他方法可以在不使用字典的情况下解决此问题。

def nonDivisibleSubset(k, s):
remdict={}
result=[]
keyss=[]
for i in range(len(s)):
rem=s[i]%k
if rem not in remdict:
remdict[rem]=1
else:
remdict[rem]+=1
#b=dict(sorted(remdict.items(), key= lambda x: len(x[1]), reverse=True))
print(remdict)
for key,value in remdict.items():
if key==0:
result.append(1)
elif key+key==k:
result.append(1)
elif (k-key) in remdict.keys() and k-key not in keyss :
print(max(remdict[key],remdict[k-key]))
keyss.append(key)
result.append(max(remdict[key],remdict[k-key]))
elif (k-key) not in remdict.keys():
print(remdict[key])
result.append(remdict[key])
print(result)
return (sum(result))