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

题目：

给n个商品的价格，然后给出优惠券满减的价格，求问可使用这张优惠券最低价格是多少。

商品总价超过优惠券价格的三倍，或者低于优惠券，返回 -1。

输入：（优惠券值m、商品个数n、n个商品的价格）

1000 4 555 500 450 460

输出：

1055

import sysline = sys.stdin.readline().strip()list_ = list(map(int, line.split()))m, n = list_[0], list_[1]nums = list_[2:]sum_ = sum(nums)dp = [0 for i in range(sum_ + 1)]if(sum_ < m):    print(-1)elif(sum_ == m):    print(m)else:    dp[0] = 1    for i in range(n):        for j in range(sum_, nums[i] - 1, -1):            dp[j] |= dp[j - nums[i]] '''有1出1，全0出0， 比if判断要快速'''    for i in range(m + 1, sum_ + 1):        if(i // m >= 3):            print(-1)            break        if(dp[i] == 1):            print(i)            break

转载地址：http://kzmfb.baihongyu.com/