跟分餐桌很像,但是写了半天还是写不出来。
描述: 餐厅有 n 张桌子,每张桌子分别可以坐 a[n]个人,今日有 m 组客人预约,每组分别有 b[m]人。对其安排座位。 -如果:
输入形式: 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
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 |