[备战秋招]3月18日美团春招+题目思路-爱代码爱编程
www.codefun2000.com 最近我们一直在将收集到的各种大厂笔试的解题思路还原成题目并制作数据,挂载到我们的OJ上,供大家学习交流,体会笔试难度。现已录入200+道互联网大厂模拟练习题,还在极速更新中。欢迎关注公众号“塔子哥学算法”获取最新消息。 提交链接:
Problem Detail - 2023.3.18.10点-第四题-提瓦特商店 - CodeFun2000
为了更好的阅读体检,可以查看OJ上的题解。进入提交链接,点击右边菜单栏的"查看塔子哥的题解"
题目内容
塔子哥是一位购物狂人,他经常光顾提瓦特商店。最近,提瓦特商店推出了一项促销活动,有N件商品打折销售。每个商品都有原价和折扣价,而且不同的商品的折扣力度也不同。
塔子哥听说了这个促销活动后非常兴奋,他计划购买尽可能多的商品,同时也希望尽量少地花钱。他掏出了自己的钱包,发现他手头有X元的现金和Y张折扣券。
于是塔子哥找到了你,希望你能帮助他计算出在这种情况下他可以购买的最多商品数量以及花费的最少钱数。
输入描述
第一行三个整数,以空格分开,分别表示N,X,Y。
接下来N行,每行两个整数,以空格分开,表示一个的原价和折扣价。
,,,每个商品原价和折扣价均介于[1,50]之间。
输出描述
一行,两个整数,以空格分开。第一个数字表示最多买几个商品,第二个数字表示在满足商品尽量多的前提下所花费的最少的钱数。
样例1
输入
2 5 1 3 1 1 1
输出
2 2
说明: 第一个商品折扣价购入,第二个商品原价购入,可以获得最多的商品数量2个。此时消耗2元。因此输出 2 2。
样例2
输入
5 10 2 10 6 5 3 7 4 4 3 15 3
输出
3 10
思路
动态规划解决.背包问题
状态:
代表在考虑前 i 个物品时花费 j 元且已经用掉了 k 个折扣券时能买到的最多的商品.
这里用 a[i] 代表第 i 个商品的原价,b[i] 代表折扣价
转移:
使用每个商品更新dp数组,考虑每个物品用或不用打折卷,有以下转移:
注意:代码实现时使用了刷表法,就是用 去更新 和 ,和上面的式子实质是一样的。
更多具体细节见代码注释
类似题目推荐
leetcode
CodeFun2000
P1113 字节跳动-暑期实习-2023.03.24-第二题-元素骰子