求基于Dynamic Programming的发票金额子集求和完整DP方案

业务场景 #

从发票提取的数字数组中，找到最大元素的子集，使其和等于数组中的某一元素。例如数组[235, 120, 340, 600, 150000, 1175]中，1175 = 235 + 340 + 600。

现有尝试 #

刚接触动态规划（DP），需要实现可规模化的方案：找出表格中所有求和等于总额的行项目，思路是找所有可能子集，求和匹配数组中的最大目标值。但现有实现存在冗余hack（如findAlt方法），当子集元素超过3个时失效，尝试代码如下：

import numpy as np

#main_arr = [ 3, 4, 1, 8, 10, 16 ]
main_arr = [ 3, 4, 1, 7, 15, 23, 25, 36 ]

sorted_arr_ = sorted( main_arr )

matrix_ = dict()

def calcMatrix():
        for outer_ in sorted_arr_:
                for inner_ in sorted_arr_:
                        if outer_ == inner_: continue
                        matrix_[ str(outer_)+'-'+str(inner_) ] = inner_ + outer_
calcMatrix()

print( matrix_ )

mem_dict_ = dict()
for ctr in range(1, max(main_arr)):
        if ctr in sorted_arr_:
                mem_dict_[ ctr ] = str(ctr)
        else:
                mem_dict_[ ctr ] = '0'

def search_matrix( balance ):
        for key, val in matrix_.items():
                if val == balance: return key

        return None
def search_mem( balance ):
        for key, val in mem_dict_.items():
                if balance == key and val != '0': return val

        return None

def findAlt( bal, avoid ):
        for idx in range( bal ):
                major, minor = idx, bal-idx
                maj, mino = None, None
                print('In findAlt->', major, minor)
                if major != avoid and minor != avoid:
                        matrix_res_major = search_matrix( major )
                        matrix_res_minor = search_matrix( minor )
                        mem_res_major = search_mem( major )
                        mem_res_minor = search_mem( minor )
                        maj = matrix_res_major if mem_res_major is None else mem_res_major
                        mino = matrix_res_minor if mem_res_minor is None else mem_res_minor
                        if maj is not None and mino is not None: return maj+mino

def recur( updated_idx, main_idx ):
        if updated_idx <= 0 : return None

        bal_ = sorted_arr_[ main_idx ] - sorted_arr_[ updated_idx-1 ]
        print( 'updated_idx, main_idx, bal_, sorted_arr_[ updated_idx ], sorted_arr_[ updated_idx-1 ] = ',\
                updated_idx, main_idx, bal_, sorted_arr_[ updated_idx ], sorted_arr_[ updated_idx-1 ] )

        pos_key_ = search_matrix( bal_ )
        pos_mem_key_bal_ = search_mem( bal_ )
        pos_mem_key_ = search_matrix( sorted_arr_[ main_idx ] )
        print( pos_key_, pos_mem_key_bal_, pos_mem_key_ )

        if pos_key_ is not None :
                if str(sorted_arr_[ updated_idx-1 ]) not in str(pos_key_):
                        mem_dict_[ sorted_arr_[ main_idx ] ] = str(pos_key_)+'-'+str(sorted_arr_[ updated_idx-1 ])
                        print('Updated mem with key (a) = ', sorted_arr_[ main_idx ], ' with str = ', \
                                str(pos_key_)+str(sorted_arr_[ updated_idx-1 ]) )
                else:
                        posKey = findAlt( bal_, sorted_arr_[ updated_idx-1 ] )
                        if posKey is not None:
                                mem_dict_[ sorted_arr_[ main_idx ] ] = str(posKey)+'-'+\
                                                                        str(sorted_arr_[ updated_idx-1 ])
                                print('Updated mem with key (a.1) = ', sorted_arr_[ main_idx ], ' with str = ', \
                                str(posKey)+str(sorted_arr_[ updated_idx-1 ]) )

        elif pos_key_ is None and pos_mem_key_bal_ is not None and str(sorted_arr_[ updated_idx-1 ]) \
                        not in str( pos_mem_key_bal_ ):
                mem_dict_[ sorted_arr_[ main_idx ] ] = str(pos_mem_key_bal_)+'-'+str(sorted_arr_[ updated_idx-1 ])
                print('Updated mem with key (b) = ', sorted_arr_[ main_idx ], ' with str = ', \
                        str(pos_mem_key_bal_)+str(sorted_arr_[ updated_idx-1 ]) )
        else:
                recur( updated_idx-1, main_idx )
for i in range( 2, len(sorted_arr_) ):
        recur( i, i )

需求 #

希望获得简洁的10-15行左右的无hack完整DP解决方案。

以下是符合要求的无hack解决方案，核心用DP字典追踪每个和对应的子集，确保能处理任意数量元素的子集：

def find_subset_sum(arr):
    sorted_arr = sorted(arr)
    dp = {0: []}
    for num in sorted_arr:
        for s in list(dp.keys()):
            new_sum = s + num
            if new_sum not in dp:
                dp[new_sum] = dp[s] + [num]
    for target in reversed(sorted_arr):
        if target in dp and len(dp[target]) > 1:
            return target, dp[target]
    return None, None

# 测试示例
print(find_subset_sum([235, 120, 340, 600, 150000, 1175]))
print(find_subset_sum([3, 4, 1, 7, 15, 23, 25, 36]))

逻辑说明 #

• 先排序数组，后续逆序查找目标值，保证找到的是数组中最大的符合条件的元素
• dp字典记录每个可能的和对应的子集，初始状态为和0对应空子集
• 遍历每个数字，更新所有可能的新和及其子集，避免重复添加相同和的子集
• 最后逆序遍历数组元素，找到第一个存在对应非单元素子集的目标值并返回

内容的提问来源于stack exchange，提问作者Vikram Murthy