介绍： 我试图解决的目标问题是一个动态编程问题，其中我获得了自然数和目标数字（TGT）的列表。该程序是使用数字...

Question

程序最终应返回原始列表中使用的数字列表，以使其靠近TGT。我的代码总体上有两个半部分，第一个功能是目标，第二个功能是第二个getBestTargetsum。 totargetsum基于连续更新的TGT递归解决子问题，这是原始目标与所考虑的数字总和之间的差异。

getBestTargetsum应该回忆起（表T），因为它称为Targetsum，并将解决方案记录到表D。我认为这是我的问题所在的地方。 sissues：

首先，我认为我的解决方案表D无法正确录制，因为它不包括我希望它的所有索引，例如（0,0）。在此代码的不同版本中，我在d中出现了负值，这可能表明诸如（0,0）之类的索引因我试图从表中摆脱负值而丢失了（0,0）。

二，此代码的结果返回与应进行的相反。当给出数字列表时，即{1、2、3、4、5、10}和a tgt = 15，而不是选择{5，10}以0的差为0，它选择并返回{1，2，5}而不是选择{1，2，5}。

这里是我的代码，请原谅我的混乱。我不过是菜鸟。 注意：钥匙应该确定表D的起点D。老实说，我遇到了很多麻烦，让我不应该做什么，更不用说它应该存在了。谢谢您的帮助。

def targetSum(S, i, tgt):
    k = len(S)
    
    if tgt < 0:
        return float('inf')
    
    if i == k and tgt >= 0: 
        return tgt
    
    else: 
        return min(targetSum(S, i+1, tgt-S[i]), targetSum(S, i+1, tgt)) 
 
       
def getBestTargetSum(S, tgt):
    
    k = len(S)
    D = {} # Solutions table
    T = {} # Memo table
        
    # Case 1: At the end
    for j in range(tgt+1):
        T[(k,j)] = j
        #D[(k,j)] = k,j

    for i in range(k-1, -1, -1):
        for j in range(tgt+1):
            # Case 2: Skip
            if j < 0:
                T[(i,j)] = float('inf')
                D[(i,j)] = i+1,j
            
            # Case 3: Choice
            else:
                include = targetSum(S, i+1, tgt-S[i])
                exclude = targetSum(S, i+1, tgt)

                if include <= exclude:
                    T[(i,j)] = include
                    if j - S[i] >= 0:
                        D[(i,j)] = (i+1, j - S[i])

                else:
                    T[(i,j)] = exclude
                    D[(i,j)] = (i+1, j)

    # Retrieving solution from D
    res = []
      
    key = 0,15
    
    while key in D:
        
        value = D[key]
        
        if value[1] != key[1]:
            i = key[0]
            res.append(S[i])
        
        key = value
        print(i,j,':',res) 
    
    return res  

您的功能似乎在做非常多余的工作。

为什么不仅使用您的第一个函数

getBestTargetSum

，然后对其进行调整以使其除了得分之外返回选定的数字列表？

targetSum