这是一个创建于 1937 天前的主题，其中的信息可能已经有所发展或是发生改变。
跟分餐桌很像，但是写了半天还是写不出来。
描述： 餐厅有 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 人桌上） 第 1 条附言 2021 年 1 月 5 日
数据范围：
0<n<14,
0<m<21,
0<x,y<1001
1<a[n],b[m]<1001
均为整数
0<n<14,
0<m<21,
0<x,y<1001
1<a[n],b[m]<1001
均为整数
第 2 条附言 2021 年 1 月 6 日
LRvx #15
yzbythesea #18
谢谢 2 位大佬的解答
yzbythesea #18
谢谢 2 位大佬的解答
 | 1 LRvx 2021 年 1 月 5 日 有数据范围吗 |
 | 3 yzbythesea 2021 年 1 月 5 日 m 和 n 也不大，直接 DFS，从人数最多的预约开始安排，安排完再搞次多的，依此类推。 |
 | 4 Wolfsin OP @yzbythesea #3 之前也有从最多的人数开始安排的打算，但是看到例 2 后发现，有直接舍弃掉一组人的最优解，所以一下又没有想法了。 他不是在求一组人的最优解，是在求几组人合在一起的最优解。想到这思绪就理不清楚了。如果可以的话，能不能提供点伪代码，或者更加具体的思路啊 |
| 5 Wolfsin OP @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 ）。 |
 | 6 xupefei 2021 年 1 月 5 日 应该是三维动态规划 |
 | 7 xupefei 2021 年 1 月 5 日 via iPhone 又想了想，这不就是 fractional multiple knapsack 么 |
| 8 LRvx 2021 年 1 月 5 日 想一想，n 和 m 的范围不大，是状态压缩后做 dp 吗 |
| 9 Wolfsin OP |
| 10 yzbythesea 2021 年 1 月 5 日  1 @Wolfsin 对于任何一个组，我们可以算出需要几个桌子，然后从而得到拒绝这个组还是分开坐，花费高，然后进行选择。从人数最多的组开始。类似贪心。 |
| 11 Wolfsin OP @yzbythesea #10 但是还有一个问题，就是贪心是通过局部最优解来导出全体最优解，这里全体最优解可能不是局部的最优解，比如例 1 的人数最多 7 人组，计算出的最优解应该是 5+4，2 张桌子，满意度下降（ 2-1 ）*y ；但是实际的全体最优解却是 5+1+1，满意度下降（ 3-1 ）*y，至于为什么不选 5+4 的最优解，是因为下一组的关系。所以单纯按组贪心，还是算不出答案 |
| 12 LRvx 2021 年 1 月 5 日 老哥有评测姬的地址吗？ |
| 13 LRvx 2021 年 1 月 5 日 写了一个 dp （ 01 背包）+状压的解，但是目前手太生了，脑子也不行了，我测一测，看看对不对 |
| 15 LRvx 2021 年 1 月 5 日 1 https://paste.ubuntu.com/p/VtbXNNyHGm/ 这个算法的复杂度在那个枚举每个状态的地方，所以时间复杂的有点大，实际上可以进行 sort 每种座子后根据一些规则进行筛选枚举每个组的不同安排情况，降低复杂度。 |
| 16 yzbythesea 2021 年 1 月 6 日 @Wolfsin 例子 1 先算 7 桌，肯定不会拒绝，然后安排可以是 5 + 4 也可以是 5 + 1 + 1 。再分别 DFS，5 + 4 这个只剩 1 + 1，对于 3 人 只能拒绝，得出 cost ； 5 + 1 + 1 只剩 4， 对于 3 人， 可以拒绝 也可以 安排， 算出 cost，完事儿。 这个不是贪心，你还是得 DFS，只是基于贪心的概念进行剪枝。我觉得你不剪枝都可以，反正 m 和 n 都不大。 |
| 17 yzbythesea 2021 年 1 月 6 日 @yzbythesea 对于拒绝和安排，只能这两个大方向剪枝，不能对安排的策略剪枝。 |
| 18 yzbythesea 2021 年 1 月 6 日 1 |
| 19 Wolfsin OP |
Select Language