Loading... # 背景 多选的应用场景。 比如在 菜品-材料-供应商 的角色中。会有这样两样的需求 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 表示储货。 | A | X | 是否可用 | ---------- | X | B | 是否可用 | | - | - | -------- | ---------- | - | - | -------- | | 0 | 0 | 1 | | 0 | 0 | 1 | | 0 | 1 | 1 | | 0 | 1 | 1 | | 1 | 0 | 0 | | 1 | 0 | 0 | | 1 | 1 | 1 | | 1 | 1 | 1 | 可以发现，A-X，X-B 的情况是一样的。这时计算 OR、AND 备用 | A | X | or | and | 是否可用 | ---------- | X | B | or | and | 是否可用 | | - | - | -- | --- | -------- | ---------- | - | - | -- | --- | -------- | | 0 | 0 | 0 | 0 | 1 | | 0 | 0 | 0 | 0 | 1 | | 0 | 1 | 1 | 0 | 1 | | 0 | 1 | 1 | 0 | 1 | | 1 | 0 | 1 | 0 | 0 | | 1 | 0 | 1 | 0 | 0 | | 1 | 1 | 1 | 1 | 1 | | 1 | 1 | 1 | 1 | 1 | 可以注意到，在可用的情况下，满足 `A or X = X`，`X and B = X` （或者说，`A and X = A`，`X 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` 等类型） ```sql 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 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏
3 条评论
ban IP，46.161.11.0/24
8 月 30 日启用 CDN 之前为 88 次，然后 CDN 日志中总计访问 13973 次，除去来自 46.161.11.0/24 的 13769 次
剩余为 88 + 13973 - 13769 = 292 次
修改数据库重置访问次数为 292 次
虽然 typecho 自动记录 15129 次...
天天扫我干嘛....
这篇文章都被扫到了一万多次
（来源：上海、天津 IP，包含某些 IDC 和家宽）