求问Airbnb的menu order

我大概先简述一下看到的面经描述：
点菜，菜价格为double, 问如何正好花完手中的钱。

可是这里有个疑问，这个问题到底是combination sum还是combination sum 2的变体？看到有的地方说是combination sum2的变体，菜的价格可以一样，也有的地方说是combination sum的变体。

多谢大家！

这一类问题一般叫做背包问题（knapsack problem），大分类上是属于经典的整数规划（integer programming）问题。

背包问题有若干种变体（参考这里：https://en.wikipedia.org/wiki/Knapsack_problem#Definition）
(1) 0-1背包 —— 每个物体只能取一次
(2) 有界背包 —— 每个物体最多可以取某个给定的次数
(3) 无界背包 —— 每个物体可以取任意多次
(4) 部分背包 —— 每个物体可以取任意部分（也就是可以取小数）

其中(4)属于线性规划问题而不是整数规划，其有多项式时间算法。

(1)(2)(3)是NP-Hard问题，但是在物品重量为整数时，有伪多项式时间算法（用动态规划）

而这里的菜单这道题目，应该属于(3)无界背包，并且物品重量不是整数（除非菜价这个double实际上是"decimal"，只取两位小数什么的）。那么是不能用动态规划的，只能用指数时间复杂度的搜索算法（DFS或者BFS）。

自己顶一下，看到glassdoor的描述好像是combination sum ii.

https://www.glassdoor.com/Interview/Airbnb-Software-Engineer-Interview-Questions-EI_IE391850.0,6_KO7,24_IP3.htm

Q) Given a list of menu items and prices. Print all combinations that match a target price.
Eg: target = $3, Menu( A:$1 , B:$2)

Print
A,A,A
A,B

同问 菜价不是整数怎么处理呢？

magicsets 发表于 2018-2-22 03:55
这一类问题一般叫做背包问题（knapsack problem），大分类上是属于经典的整数规划（integer programming） ...

给你点个赞

magicsets 发表于 2018-2-22 03:55
这一类问题一般叫做背包问题（knapsack problem），大分类上是属于经典的整数规划（integer programming） ...

太牛了！zszszszs