这是一个创建于 1454 天前的主题，其中的信息可能已经有所发展或是发生改变。
跟分餐桌很像，但是写了半天还是写不出来。
描述： 餐厅有 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-01-05 19:38:12 +08:00
数据范围：
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-01-06 22:54:51 +08:00
LRvx #15
yzbythesea #18
谢谢 2 位大佬的解答
yzbythesea #18
谢谢 2 位大佬的解答
 |
1
LRvx 2021-01-05 19:31:18 +08:00
有数据范围吗
|
 |
3
yzbythesea 2021-01-05 19:55:03 +08:00
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-01-05 20:13:17 +08:00
应该是三维动态规划
|
|
7
xupefei 2021-01-05 20:20:21 +08:00 via iPhone
又想了想，这不就是 fractional multiple knapsack 么
|
|
8
LRvx 2021-01-05 20:41:49 +08:00
想一想，n 和 m 的范围不大，是状态压缩后做 dp 吗
|
|
9
Wolfsin OP |
|
10
yzbythesea 2021-01-05 21:18:16 +08:00  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-01-05 21:44:46 +08:00
老哥有评测姬的地址吗？
|
|
13
LRvx 2021-01-05 21:55:25 +08:00
写了一个 dp （ 01 背包）+状压的解，但是目前手太生了，脑子也不行了，我测一测，看看对不对
|
|
15
LRvx 2021-01-05 22:28:20 +08:00 1
https://paste.ubuntu.com/p/VtbXNNyHGm/ 这个算法的复杂度在那个枚举每个状态的地方，所以时间复杂的有点大，实际上可以进行 sort 每种座子后根据一些规则进行筛选枚举每个组的不同安排情况，降低复杂度。
|
|
16
yzbythesea 2021-01-06 03:17:32 +08:00
@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-01-06 03:19:43 +08:00
@yzbythesea 对于拒绝和安排，只能这两个大方向剪枝，不能对安排的策略剪枝。
|
|
18
yzbythesea 2021-01-06 09:02:44 +08:00 1
|
|
19
Wolfsin OP |
Select Language