# 沁原每日面经解读 001

- 资料整理：www.bittiger.io

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

[![](http://img.youtube.com/vi/xsx4oF1hPks/0.jpg)](http://www.youtube.com/watch?v=xsx4oF1hPks "")


### 题目

```

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


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

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

```

### 思路

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