背景

多选的应用场景。

比如在 菜品-材料-供应商 的角色中。会有这样两样的需求

  1. 在有材料 X({x1, x2 ...})的情况下,可以做出哪些菜品(A1, A2, A3...分别需要 {a11, a12...}, {a21, a22...}, {a31, a32}... 的原材料)
  2. 在需要材料 X({x1, x2 ...})的情况下,选择哪家供应商可以一次性采购完全(B1, B2, B3...)

对于问题 1,即找到 $A_i \sub X$ 的全部的 $A_i$

对于问题 2,即找到 $X \sub B_i$ 的全部 $B_i$

计算

这些数据是放到 MySQL 中的,可选项(食材)不是很多,暂定比如 20 样。但是菜品的可选项以及供应商的可选项很多($2^{20} = 1048576$),开始时,采用的是 JSON 字段类型,通过 JSON_CONTAINS 进行判断。

但是这个在需求 2 勉强可以满足(对于 $x_i$ 依次进行筛选,选完包含 $x_1$ 的,然后继续筛选包含 $x_2$ 的,等等这样依次进行下去,直到全部选择完成。)

而对于需求 1 似乎无解(对于食材需要 $a$ 但是当前储备没有 $a$ 的情况的时候,很难进行判断)

后来偶然考虑到了位运算

位运算

先看一样食材 a

分别用 0、1 表示需要/储备/满足需求、不需要/未储备/不满足需求 两个情况。A 表示食材需求,B 表示供应商,X 表示储货。

AX是否可用----------XB是否可用
001 001
011 011
100 100
111 111

可以发现,A-X,X-B 的情况是一样的。这时计算 OR、AND 备用

AXorand是否可用----------XBorand是否可用
00001 00001
01101 01101
10100 10100
11111 11111

可以注意到,在可用的情况下,满足 A or X = XX and B = X (或者说,A and X = AX or B = B

上面是只有一种材料的情况下。而当位数扩展后,从逻辑运算扩展到位运算,依然满足这个性质。

  1. 在有材料 X({x1, x2 ...})的情况下,可以做出哪些菜品(A1, A2, A3...分别需要 {a11, a12...}, {a21, a22...}, {a31, a32}... 的原材料)
    A or X = X, A and X = A
  2. 在需要材料 X({x1, x2 ...})的情况下,选择哪家供应商可以一次性采购完全(B1, B2, B3...)
    B and X = X, B or X = B

因此可以考虑 MySQL 实现。(为了方便显示,使用了 bit 类型,实际上可以用 int 等类型)

drop table if exists `food`;
drop table if exists `supply`;
create table `food`(
    ​`need` bit(3)
); 

insert into `food` (`need`) values
(B'000'), (B'001'), (B'010'), (B'011'), (B'100'), (B'101'), (B'110'), (B'111');

create table `supply` (
    `goods` bit(3)
);

insert into `supply` (`goods`) values
(B'000'), (B'001'), (B'010'), (B'011'), (B'100'), (B'101'), (B'110'), (B'111');

-- 假设储货为 110,可以做到的食物为 000, 010, 100, 110
select * from `food` where `need` | (B'110') = (B'110');

-- 假设需求为 110,则可以满足的供应商为 110, 111
select * from `supply` where `goods` & (B'110') = (B'110');
最后修改:2021 年 10 月 16 日
如果觉得我的文章对你有用,请随意赞赏