本文共 1393 字，大约阅读时间需要 4 分钟。

??????????????????????????????????????5???????????????????

????

????

import sys
def main():
    for line in sys.stdin:
        n = int(line.strip())
        if n == 0:
            break
        a = []
        while len(a) < n:
            a.append(int(sys.stdin.readline()))
        m = int(sys.stdin.readline())
        if m < 5:
            print(m)
            continue
        max_price = max(a) if a else 0
        sum_a = sum(a)
        target = m + 5 + sum_a
        dp = [-1] * (target + 1)
        dp[0] = 0
        for num in a:
            for j in range(target, num - 1, -1):
                if dp[j - num] != -1:
                    if dp[j] < dp[j - num] + num:
                        dp[j] = dp[j - num] + num
        best = -1
        for j in range(5, target + 1):
            if dp[j] != -1 and dp[j] > best:
                best = dp[j]
        if best == -1:
            print(m)
        else:
            print(m - best)
if __name__ == "__main__":
    main()

????

• ???????????????????n=0?
• ??????????????m??5?????m?
• ??????????????dp?????????????????
• ???????????????????????dp???
• ?????????????T???T >= 5???????????????

?????????????????????????????????