算法题写不出来，不知道有没有大佬给个思路。

[Wolfsin]

跟分餐桌很像，但是写了半天还是写不出来。

---

描述： 餐厅有 n 张桌子，每张桌子分别可以坐 a[n]个人，今日有 m 组客人预约，每组分别有 b[m]人。对其安排座位。 -如果：

• 一组客人都安排在一张桌子上，那么满意度不会下降。
• 如果拒绝这组客人的预约，那么满意度下降：人数 * x
• 如果将一组客人分在 k 张桌子上用餐，那么满意度下降：(k-1) * y
  • 比如说有 4 人桌，5 人桌，1 人桌，1 人桌 4 张桌子，y=10 的情况下，将 7 人的一组客人，分到 4，5 2 张桌子的情况，满意度下降(2-1) * 10 。或者将其分成 5,1,1 3 张桌子的情况，满意度下降(3-1) * 10 。
• 不能与其他组的客人拼桌

输入形式： n m x y a[1] a[2] … a[n] b[1] b[2] … b[n]

例 1：

输入:
4 2 5 3 
4 5 1 1
7 3
输出
6 （ 7 人组：分到 5 1 1 桌上，3 人组分到 4 人桌上）

例 2：

输入
4 2 2 16
4 5 1 1
7 3
输出
14 （ 7 人组：拒绝预约，3 人组：分到 4 人桌上）

例 3：

输入
4 2 5 3
1 1 2 3
2 5
输出
6 （ 2 人组：1，1 桌上，5 人组：分到 2，3 人桌上）

[LRvx]

有数据范围吗

[Wolfsin]

@LRvx #1 在附言里更新了

[yzbythesea]

m 和 n 也不大，直接 DFS，从人数最多的预约开始安排，安排完再搞次多的，依此类推。

[Wolfsin]

@yzbythesea #3 之前也有从最多的人数开始安排的打算，但是看到例 2 后发现，有直接舍弃掉一组人的最优解，所以一下又没有想法了。
他不是在求一组人的最优解，是在求几组人合在一起的最优解。想到这思绪就理不清楚了。如果可以的话，能不能提供点伪代码，或者更加具体的思路啊

[Wolfsin]

@yzbythesea #3 根据 x 和 y 的数值，也会产生新的变化，如果不考虑 x 和 y 的话，7 人的最佳排法肯定是 5+4，考虑到下一组有 3 人，那么这么排就需要拒绝掉 3 人（满意度下降（ 2-1 ）*y+3*x ）；或者说 7 人采取次佳的排法 5+1+1，下一组可以排 4 人的那张桌子（例 1，满意度下降（ 3-1 ）*y ）；但是在例 2 中，x 远小于 y，这时候例 1 的排法就不是最优解了（例 2 的情况，满意度下降 7*x ）。

[xupefei]

应该是三维动态规划

[xupefei]

又想了想，这不就是 fractional multiple knapsack 么

[LRvx]

想一想，n 和 m 的范围不大，是状态压缩后做 dp 吗

[Wolfsin]

@xupefei #7 的确应该算背包问题，但是贪心算法在这里并不是很好用。
@LRvx #8 dp 我也考虑了一下，最后因为时间不够了没有仔细想下去。
我最后的思路只剩下去算全部的可能性和其对应的下降值，但是写的途中也遇到了问题，因为理不清楚顺序，如果是不考虑复杂度，只是暴力去解的话，代码应该怎么写比较好呢？

[yzbythesea]

@Wolfsin 对于任何一个组，我们可以算出需要几个桌子，然后从而得到拒绝这个组还是分开坐，花费高，然后进行选择。从人数最多的组开始。类似贪心。

[Wolfsin]

@yzbythesea #10 但是还有一个问题，就是贪心是通过局部最优解来导出全体最优解，这里全体最优解可能不是局部的最优解，比如例 1 的人数最多 7 人组，计算出的最优解应该是 5+4，2 张桌子，满意度下降（ 2-1 ）*y ；但是实际的全体最优解却是 5+1+1，满意度下降（ 3-1 ）*y，至于为什么不选 5+4 的最优解，是因为下一组的关系。所以单纯按组贪心，还是算不出答案

[LRvx]

老哥有评测姬的地址吗？

[LRvx]

写了一个 dp （ 01 背包）+状压的解，但是目前手太生了，脑子也不行了，我测一测，看看对不对

[Wolfsin]

@LRvx #13 抱歉，没有 oj，只能脑测。如果可以的话，能分享一下代码吗？

[LRvx]

https://paste.ubuntu.com/p/VtbXNNyHGm/ 这个算法的复杂度在那个枚举每个状态的地方，所以时间复杂的有点大，实际上可以进行 sort 每种座子后根据一些规则进行筛选枚举每个组的不同安排情况，降低复杂度。

[yzbythesea]

@Wolfsin 例子 1 先算 7 桌，肯定不会拒绝，然后安排可以是 5 + 4 也可以是 5 + 1 + 1 。再分别 DFS，5 + 4 这个只剩 1 + 1，对于 3 人 只能拒绝，得出 cost ； 5 + 1 + 1 只剩 4， 对于 3 人， 可以拒绝 也可以 安排， 算出 cost，完事儿。

这个不是贪心，你还是得 DFS，只是基于贪心的概念进行剪枝。我觉得你不剪枝都可以，反正 m 和 n 都不大。

[yzbythesea]

@yzbythesea 对于拒绝和安排，只能这两个大方向剪枝，不能对安排的策略剪枝。

[yzbythesea]

写了一下 DFS 的方法，跑了三个例子都对，不知道还有没有别的例子。没有从最多的人数的组开始安排，也可以。

https://paste.ubuntu.com/p/cnbZqjqWwY/

[Wolfsin]

@LRvx #15
@yzbythesea #18
谢谢楼上 2 位大佬的解答