Fork me on GitHub

vivo 2022 届提前批数据挖掘 面试题 | 文末免费送书

第 1 题:输入一个数组,统计数组中有多少个数是7的倍数或者含有数字7

判断一个数是否是7的倍数可以直接用取余的方法,判断一个数中是否含有数字7,这里提供两种方法:一种是将数字转换成字符串,用 in 进行判断;另一种是将数字转换成字符串,用 find 方法,如果不包含会返回 -1。

代码如下:

2021年6月22日,vivo 2022届提前批数据挖掘 面试题

第2题:0-1背包问题

题目描述: 给定物品的重量weights=[1, 2, 5, 6, 7] ,对应的价值values=[1, 6, 18, 22, 28] , 背包能装的最大重量为capicity=11。问:我们用这个背包装什么物品能获得最大价值? 注意:每件物品只有一件。并且最终重量不能超过背包所能承载的重量。

本题解析参考:https://www.pianshen.com/article/2073277310/

分析:

首先,说明一下,本题采用动态规划, 因为问题的本身含最优子结构。 我们先给出转态转移方程:

2021年6月22日,vivo 2022届提前批数据挖掘 面试题

c(i, w)表示包容量为w时,考虑前i个物品所能获得的最大价值。。i表示第i个物品,w表示包容量;

**第―种情况︰**当前物品的重量超过了包的承载量,显然装不上,那它当前的最大价值就是原有包中的价值(不装这个物品时的最大价值)。

**第二种情况︰**当前物品的重量没有包承载量大。则说明当前这个物品可以装进去。那我们就得考虑了︰装这个物品价值大还是不装这个物品价值大?﹑从两种情况中选最大的。

2021年6月22日,vivo 2022届提前批数据挖掘 面试题
右下角的40,就是我们所能获得的最大价值

接着,我们还需要输出获得最大价值的时候,我们拿了什么物品。

2021年6月22日,vivo 2022届提前批数据挖掘 面试题

从右下角的40开始,背包容量为11,由于40与上一行的40相等,说明我们没有装第五个物品(因为当背包容量为11,装第四个物品的时候,价值已经到达了40)。紧接着,在背包容量为11时,对应第三个物品,最大价值是25,所以,我们装了第四个物品。此时,我们的背包容量变为W-w4即:11-6=5。所以,对于第三个物品,我们直接考虑在背包容量为5的时候,可以看出价值是18,考虑有没有装第三个?因为背包容量为5时,第二个物品所对应的最大价值为7.所以我们装了第三个物品。接在:W剩– w3= 5-5 =0。我们就可以得出背包中装了第三个和第四个物品。

代码实现:

2021年6月22日,vivo 2022届提前批数据挖掘 面试题

七月在线AI充电季,开宝箱活动正在进行中 ,200本AI纸质书、机械键盘、硬盘、VIP会员,来就送~

活动截止时间:7月31日 15:00

活动链接:https://www.julyedu.com/active/treasure


本文地址:https://www.6aiq.com/article/1627406355143
本文版权归作者和AIQ共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出