001.md

沁原每日面经解读 001

• 资料整理：www.bittiger.io

偷蛋糕 AQR-全职-在线笔试-应届

题目

你是一个偷蛋糕的小偷，每种蛋糕有一个重量和价值，而且每种蛋糕都有无限个。
你最多能拿走重量为x的蛋糕，请问能偷走的最大价值是多少？


例如，我们有两种蛋糕：
(7千克, 160元)
(3千克, 90元)

最多能够装13千克，那么最大价值是90*4=360

思路

• 遍历模型：经典的背包问题，可以使用性价比进行剪枝搜索
• 演绎模型：基于重量<=k的最大价值，推导出重量为k+1的最大值