这不是家庭作业问题这是我们在开发在线产品时面临的一个问题。希望有人能告诉我这是不是一个一般的算法问题。
假设我有4个房间：
1号房间-2人-800
2个房间-3人-1400
3号房间-2人-1000
4号房间-2人-2000
假设我想以最低的成本容纳4个人。
理想情况下我应该是1号房间+3号房间
我试着用价格/人来解决这个问题，但那会失败，因为它会产生1号房间和2号房间的输出
请告诉正确的算法来解决这个问题
最佳答案
正如理查德在评论中正确指出的那样，这类似于背包。然而，很容易适应pseudo-polynomial dynamic programming solution from it。
假设你有N个房间和M个人。创建一个长度为m+1的向量C，对于i>0，元素初始化为P[i]=∞，P[0]=0c的第i个条目包含找到的至少可以容纳i个人的最佳选项。
现在执行三重循环：
把每个房间都围起来。假设当前考虑的房间可以容纳p人，成本为c。
每i=0，…，m
对于每个j=i，…，min（m，i+p）
更新p[j]=min（p[j]，p[i]+c）
查看P[m]了解最佳解决方案的成本。
假设这里所有的数学成本都是常数，这有复杂度（nm2）。
找到一套最理想的房间，而不仅仅是它们的总成本，基本上是一样的在矢量中，添加两个附加项：一个用于更新该项的最后一个房间，另一个用于更新该项的最后一个房间。
关于algorithm - 根据价格最佳分配酒店房间，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/39875160/