刀大师电面

您好！
本帖隐藏的内容需要积分高于 150 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 150 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

谢谢楼主分享，看描述应该是属于knapsack problem，力扣上没有原题，但是google搜一下knapsack problem leetcode能看到一些discussion

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

匿名者 发表于 2022-2-27 04:11
谢谢楼主分享，看描述应该是属于knapsack problem，力扣上没有原题，但是google搜一下knapsack problem lee ...

又看了下，有一点不同，就是可以食物可以重复选择，所以recursion里又要从index 0开始找

感觉可以按照 (卡路里/价格) 进行排序，然后直接遍历就行了吧？

匿名者 发表于 2022-3-4 14:44
感觉可以按照 (卡路里/价格) 进行排序，然后直接遍历就行了吧？

应该不行的，同样的价格可以有不同卡路里，反过来同理，楼上有人说了是背包问题

分享一个背包问题的分析帖子 https://github.com/youngyangyang ... 83%8C%E5%8C%85-1.md

同样的物体(食物)若不能重复选择就是01背包问题，这题允许重复选择，所以是多重背包问题。都是经典问题，可以google下经典DP解法。