首页 > 试题广场 >

薯券使用问题

[编程题]薯券使用问题

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

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

输出 :组合数

输入薯券金额、商品分别价格
例如：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]

算法知识视频讲解

小菜鸡157

发表于 2020-06-09 17:07:00

动态规划： f(i,j)表示选择前i种商品构成消费券价值为j的方案数量，price_i表示第i种商品的价格。状态转移： f(i,j) = f(i-1,j)+ f(i-1,j-1price_i)...+f(i-1,j-kprice_i), k=(j/price_i) 因为 f(i,j-pr 展开全文

C++工程师测试开发工程师小红书 2020 Java工程师

上传者：小小

难度：

22条回答 148收藏 8594浏览

薯券使用问题

扫一扫，把题目装进口袋