求最大加权子集，使子集中的任意两个元素之和不等于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

其思想是根据被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))