如何将"coin changing problem"应用于熊猫数据帧？

Question

下面的问题通常有几个名称，并且有大量可用的文献。不幸的是，我对Python有点陌生，需要一些帮助才能将解决方案应用到我的案例中。

我有一个包含大约40000行的pandas数据帧，所以优化可能是一个因素。数据帧包含几列对象代码，以及一列美元金额。我想证明，这些美元金额的一个特定子集的总价值是给定的。换句话说，我想证明以下几点：

IN: 
Target: $11.72
Code1    Code2   Code3    Amount
RG22     331     ZAV      $2.00     
XG11     542     TAM      $4.23
RG22     117     GEE      $6.81
RG76     956     ZXA      $2.91
ZZ99     223     TTQ      $11.99
BW32     454     PBC      $9.35

OUT:
Code1    Code2   Code3    Amount
RG22     331     ZAV      $2.00   
RG22     117     GEE      $6.81
RG76     956     ZXA      $2.91

大多数解决方案(包括这个伟大的解决方案，下面的代码(只接受并返回值列表。我需要一个解决方案，将再现的目标代码。请建议，谢谢！

def subset_sum(numbers, target, partial=[]):
s = sum(partial)
# check if the partial sum is equals to target
if s == target: 
print "sum(%s)=%s" % (partial, target)
if s >= target:
return  # if we reach the number why bother to continue
for i in range(len(numbers)):
n = numbers[i]
remaining = numbers[i+1:]
subset_sum(remaining, target, partial + [n]) 

if __name__ == "__main__":
subset_sum([3,9,8,4,5,7,10],15)
#Outputs:
#sum([3, 8, 4])=15
#sum([3, 5, 7])=15
#sum([8, 7])=15
#sum([5, 10])=15

Answer 1

当您将您的金额(总计11.72(作为一个列表时，例如，由于以下原因获得：

def subset_sum(numbers, target, partial=[]):
s = sum(partial)
if s == target: 
return partial
if s > target:
return None # if we reach the number why bother to continue
for i in range(len(numbers)):
n = numbers[i]
remaining = numbers[i+1:]
result = subset_sum(remaining, target, partial + [n]) 
if result:
return result
amounts = subset_sum(df.Amount.tolist(), 11.72)

您可以很容易地筛选包含这些金额的行：

print(df[df.Amount.isin(amounts)])