27401: 最佳凑单

dp, sparse bucket, http://cs101.openjudge.cn/practice/27401/

消费者为了享受商家发布的满减优惠，常常需要面临凑单问题。

假设有n件商品，每件的价格分别为p1,p2,…,pn，每件商品最多只能买1件。为了享受优惠，需要凑单价为t。那么我们要找到一种凑单方式，使得凑单价格不小于t（从而享受优惠），同时尽量接近t。被称为“最佳凑单”

如果不存在任何一种凑单方式，使得凑单价格不小于t（即无法享受优惠），那么最佳凑单不存在。

比如当前还差10元享受满减，可选的小件商品有5件，价格分别为3元、5元、8元、8元和9元，每件商品最多只能买1件。那么当前的最佳凑单就是11元（3元+8元）。

输入

第一行输入商品数n（n <= 100），和需要凑单价t。第二行输入每件商品的价格。

输出

如果可以凑单成功，则输出最佳凑单的价格。如果无法凑单成功，则输出0。

样例输入

Sample1 Input:
5 10 
3 5 8 8 9

Sample1 Output:
11

样例输出

Sample2 Input:
10 89
90 10 10 10 10 5 5 3 4 1

Sample2 Output:
90

提示 tag: dp

python

# 23n1900014516 王宇佳	城市与环境学院, 27401:最佳凑单
n, v = map(int, input().split()) # 商品数，凑单价
a = list(map(int, input().split())) # 商品价格
sum_a = sum(a)
dp = [[-float("inf")] * (sum_a + 1) for _ in range(n + 1)]
dp[0][0] = 0

for i in range(1, n + 1):  # 商品数
    for j in range(sum_a + 1):  # 价格，也是重量
        if a[i - 1] <= j:
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - a[i - 1]] + a[i - 1])
        else:
            dp[i][j] = dp[i - 1][j]

if sum_a < v:
    print("0")
else:
    for k in range(v,sum_a+1):
        if dp[n][k] > 0:
            print(dp[n][k])
            break

python

# 稀疏桶
a, b = map(int, input().split())
c = {0}
for i in map(int, input().split()):
    for j in c.copy():
        if j < b: c.add(i + j)
for i in sorted(c):
    if i >= b: print(i);exit()
print(0)

27401: 最佳凑单 ​

27401: 最佳凑单