薯券使用问题

[编程题]薯券使用问题

热度指数：3011 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

某小红薯在小红书的活动中抽奖中了一定价值的薯券，这些薯券可以用来购买一批商品，求有多少种购买组合。其中一件商品可以买多件。

输入:薯券金额、商品分别价格

输出 :组合数

输入描述:

输入薯券金额、商品分别价格
例如：10 [2,3,5]
10与[2,3,5]中间有空格

输出描述:

输出4，则结果集可以为:2,2,2,2,2；5,5；2,3,5；2,2,3,3共有4种组合

示例1

输入

10 [2,3,5]

输出

算法知识视频讲解

Python

小菜鸡157

动态规划：

f(i,j)表示选择前i种商品构成消费券价值为j的方案数量，price_i表示第i种商品的价格。

状态转移：

f(i,j) = f(i-1,j)+ f(i-1,j-1*price_i)...+f(i-1,j-k*price_i), k=(j/price_i)

因为

f(i,j-price_i) = f(i-1,j-price_i)+.....+f(i-1,j-k*price_i)

故状态转移方程：

f(i,j) = f(i-1,j)+f(i,j-price_i)

str1 = input()
arr = str1.split()
# 购物券的价格
money = int(arr[0])  
# 获取商品的价格列表
price = [int(i) for i in arr[1] if i.isdigit()]
# 商品列表长度
n = len(price)
# 记录状态值
dp = [[0 for i in range(money+1)]for j in range(n+1)]
for i in range(1,n+1):
    dp[i][0] = 1  # 给定初始值
for i in range(1,n+1):
    for j in range(1,money+1):
        dp[i][j] = dp[i-1][j]
        if j>=price[i-1]:
            dp[i][j]+=dp[i][j-price[i-1]]
print(dp[-1][-1])

但是只能通过90%的案例，最后一个结果案例的结果比较大，应该要对其取相应的余数，但是题目没有告诉。

发表于 2020-06-09 17:00:49 回复(1)