在字典中找到最好的下一个键值适合约束

Question

我有一本包含 names:weights 奶牛的字典。

cows = {'Herman': 7, 'Moo Moo': 3, 'Betsy': 9, 'Lola': 2, 'Milkshake': 2, 'Florence': 2, 'Henrietta': 9, 'Maggie': 3, 'Millie': 5, 'Oreo': 6}

我必须使用贪婪算法从这本词典中创建一个列表列表。每个子列表都有一个约束：重量限制为 10。这意味着，我必须先 select 重量最大的奶牛，然后找到适合子列表的下一头奶牛。例如，这本字典问题的正确答案是：

[ ['Betsy'],
['Henrietta'],
['Herman', 'Moo Moo'],
['Oreo', 'Maggie'],
['Millie', 'Florence', 'Milkshake'],
['Lola']]

我正在尝试创建一个函数来找到下一个最适合子行程的函数。例如，如果子列表的第一个元素是 'Herman'（7 吨的重量），我需要找到最适合接近 10 的值的下一个键，在这种情况下是 'Moo Moo' （重量3吨）。所以，这是我为找到下一个匹配项而编写的函数：

def findNextFit(adict, val, limit=10):             
       v=list(adict.values())               # list of the dict's values
       k=list(adict.keys())                 # list of the dict's keys
       diff = limit - val                   # value we are looking for

       if diff in v:                        # Perfect fit.
           return k[diff]

       elif diff not in v or diff < 0:      # No fit. 
           return False

       else:               # Difference is positive but not a perfect fit
           vfit = [i for i in v if i < diff]    # list of candidates
           return k[max(vfit)]                  # key with maximum value

当我测试这个函数时，我得到了一个意想不到的结果：

>>> findNextFit(cows, 7, 10)
'Lola'

我应该得到结果的地方 'Moo Moo'。

任何人都可以指出我在这个 findNextFit 函数中做错了什么？我整天都在研究它，但我运行没主意了。

Answer 1

当你有完美契合时，你必须在 v 中的值的索引位置获取 k 中的元素，因此你缺少索引查找：

   if diff in v:                        # Perfect fit.
       return k[v.index(diff)]

您将遇到的其他问题与您的下一个测试相关联，如果第一个测试为假，下一个测试将始终 True。您的 else 子句无法访问。

Answer 2

您的问题在这里：

 if diff in v:                        # Perfect fit.
       return k[diff]

diff 不一定是值为 diff 的条目的相应键所在的索引。

您可以使用 index* 方法解决此问题：

if diff in v:
    return k[v.index(diff)]

同样在你的第三个条件中你必须做的：return k[v.index(max(fit))]

另外你的第二个条件不应该是 or 而应该是 and。

所有修复：

def findNextFit(adict, val, limit=10):             
     v=list(adict.values())               # list of the dict's values
     k=list(adict.keys())                 # list of the dict's keys
     diff = limit - val                   # value we are looking for

     if diff in v:                        # Perfect fit.
         return k[v.index(diff)]

     elif diff < 0:      # No fit. Don't need to check if diff not in v because earlier if wouldve caught this case
         return False

     else:               # Difference is positive but not a perfect fit
         vfit = [i for i in v if i < diff]      # list of candidates
         if not vfit: return False
         return k[v.index(max(vfit))]                  # key with maximum value

Answer 3

倒转奶牛可能更好:

cows = {'Herman': 7, 'Moo Moo': 3, 'Betsy': 9, 'Lola': 2, 'Milkshake': 2, 'Florence': 2, 'Henrietta': 9, 'Maggie': 3, 'Millie': 5, 'Oreo': 6}

作为

{2: ['Lola', 'Milkshake', 'Florence'], 3: ['Moo Moo', 'Maggie'], 5: ['Millie'], 6: ['Oreo'], 7: ['Herman'], 9: ['Betsy', 'Henrietta']}

那么你可以把你的函数写成：

cows = {'Herman': 7, 'Moo Moo': 3, 'Betsy': 9, 'Lola': 2, 'Milkshake': 2, 'Florence': 2, 'Henrietta': 9, 'Maggie': 3, 'Millie': 5, 'Oreo': 6}

def invert(d):
    i={}
    for k,v in d.iteritems():
        i.setdefault(v,[]).append(k)
    return i

inverted_cows = invert(cows)
# inverted_cows is a dictionary that has weights as keys and lists of cows as values

def findNextFit(adict, val, limit=10):
       diff = limit - val                   # value we are looking for

       if diff in adict:                        # Perfect fit.
           return adict[diff][0]

       elif diff <= 0:      # No fit. 
           return False

       else:               # Difference is positive but not a perfect fit
           vfit = [i for i in adict if i < diff]    # list of candidates
           if not vfit:
               return False
           return adict[max(vfit)][0]                  # key with maximum value

print findNextFit(inverted_cows, 7, 10)

这会打印 Moo Moo。由于我们比较贪心，拿了同样重量的两头牛中的第一头。

在字典中找到最好的下一个键值适合约束

Find the best next key in a dictionary which value fits in a constrain

python

algorithm

list

dictionary

greedy