找到最佳尺寸组合的算法

Question

我正在寻找一种算法来找到最佳尺寸组合以实现所需的结果.

以下面的例子为例:

|   A    |    B   |   C   |  y  |
|--------|--------|-------|-----|
| dog    | house1 | green | 30  |
| dog    | house1 | blue  | 15  |
| cat    | house1 | green | 20  |
| cat    | house2 | red   |  5  |
| turtle | house3 | green | 50  |

A,B,C是测量的尺寸.y是测量结果.

如果我想得到y> = 50的所有维度组合,那么结果将是:

turtle, house3, green
turtle, any,    green
turtle, house3, any
turtle, any,    any
any,    house3, green
any,    house3, any
any,    any,    green
any,    house1, green
any,    house1, any

也许这是一个简单的问题,但我试图用O(n)来找出最佳解决方案,但我没有找到它.

Answer 1

8 年后回到这里，使用 ClickHouse 回答这个问题：

\n

WITH table AS (\n    SELECT \'dog\' AS a, \'house1\' AS b, \'green\' AS c, 30 AS y\n    UNION ALL\n    SELECT \'dog\' AS a, \'house1\' AS b, \'blue\' AS c, 15 AS y\n    UNION ALL\n    SELECT \'cat\' AS a, \'house1\' AS b, \'green\' AS c, 20 AS y\n    UNION ALL\n    SELECT \'cat\' AS a, \'house2\' AS b, \'red\' AS c,  5 AS y\n    UNION ALL\n    SELECT \'turtle\' AS a, \'house3\' AS b, \'green\' AS c, 50 AS y\n)\nSELECT a, b, c, sum(y) y FROM table GROUP BY CUBE(a, b, c)\nHAVING y >= 50\nFORMAT PrettyCompactMonoBlock;\n\n\xe2\x94\x8c\xe2\x94\x80a\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\xac\xe2\x94\x80b\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\xac\xe2\x94\x80c\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\xac\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80y\xe2\x94\x80\xe2\x94\x90\n\xe2\x94\x82 turtle \xe2\x94\x82 house3 \xe2\x94\x82 green \xe2\x94\x82  50 \xe2\x94\x82\n\xe2\x94\x82 turtle \xe2\x94\x82 house3 \xe2\x94\x82       \xe2\x94\x82  50 \xe2\x94\x82\n\xe2\x94\x82 turtle \xe2\x94\x82        \xe2\x94\x82 green \xe2\x94\x82  50 \xe2\x94\x82\n\xe2\x94\x82 turtle \xe2\x94\x82        \xe2\x94\x82       \xe2\x94\x82  50 \xe2\x94\x82\n\xe2\x94\x82        \xe2\x94\x82 house3 \xe2\x94\x82 green \xe2\x94\x82  50 \xe2\x94\x82\n\xe2\x94\x82        \xe2\x94\x82 house1 \xe2\x94\x82 green \xe2\x94\x82  50 \xe2\x94\x82\n\xe2\x94\x82        \xe2\x94\x82 house3 \xe2\x94\x82       \xe2\x94\x82  50 \xe2\x94\x82\n\xe2\x94\x82        \xe2\x94\x82 house1 \xe2\x94\x82       \xe2\x94\x82  65 \xe2\x94\x82\n\xe2\x94\x82        \xe2\x94\x82        \xe2\x94\x82 green \xe2\x94\x82 100 \xe2\x94\x82\n\xe2\x94\x82        \xe2\x94\x82        \xe2\x94\x82       \xe2\x94\x82 120 \xe2\x94\x82\n\xe2\x94\x94\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\xb4\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\xb4\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\xb4\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x98\n

\n