如何解决涉及DP与递归的餐厅桌位分配最小成本算法问题

一家餐厅有m张桌子，每张桌子可容纳aᵢ人；有n组客人前来就餐，每组客人有bᵢ人。你可以选择接待或拒绝某组客人：

• 若拒绝该组客人，成本为 bᵢ * x
• 若接待该组客人，若需拆分到k张桌子就坐，成本为 (k−1)*y，且每张桌子仅能被一组客人使用

请计算最小总成本。

示例 #

m  n  x  y
5  2  5  3

a[] = {4,5,1,1,1}
b[] = {7,3}
output：6

示例解释 #

第二组客人坐第1张桌，第一组坐第2、3、4张桌，成本为(3-1)*3=6。

我的尝试 #

我多次尝试解决这个问题，起初认为这是动态规划（DP）问题，但无法推导状态转移方程，示例似乎无最优子结构；后尝试递归枚举所有可能性，也未成功实现。

内容的提问来源于stack exchange，提问作者wangyhpp