Big Query에서 탐욕법을 실시하다

네, 그것도 좋아요.라고 11일째 보도한 바 있다.

TL;DR

머신러닝 시스템 등 예측 결과를 보면 조합을 최적화하고 싶은 경우가 있다고 생각한다.
이 페이지에서는 SQL을 이용한 탐욕법의 구현에 대해 설명합니다.탐욕법이라 가장 적합한 해법을 얻지 못하지만 계산 원가로 저렴하니 소개해 드릴게요.
또 이번 시행 때는 빅큐리를 사용했다.

탐욕법으로 해결된 문제

괜찮은 데이터 세트를 찾을 수 없어서 끈적끈적한 방법으로 했어요.
간식의 분류 예산에 따라 결정될 때 간식 구매의 무게가 가장 큰 조합을 찾고 있다.입력표는 두 가지가 있는데 하나는 간식의 가격, 무게, 종류이고, 다른 하나는 종류별 예산을 보류하는 것이다.

입력 1: 간식당 데이터

item
item_type
item_weight
price
• 바나나
과일.
150
50
다래
과일.
110
40
딸기.
과일.
50
30
초콜릿 쵸콜렛
단맛
40
30
과자 과자
단맛
10
20
껌.
단맛
20
30
감자칩
간식
30
60
돈까스
간식
15
20
껌.
간식
15
30

입력 2: 예산별

item_type
budget
과일.
70
단맛
50
간식
60

SQL

일원의 무게가 높은 순서에 따라 고르다.

with items AS (
    SELECT
        "バナナ" AS item, "フルーツ" AS item_type, 150 AS item_weight, 50 AS price
    UNION ALL
    SELECT
        "キウイ", "フルーツ", 110, 40
    UNION ALL
    SELECT
        "イチゴ", "フルーツ", 50, 30
    UNION ALL
    SELECT
        "チョコレート", "甘味", 40, 30
    UNION ALL
    SELECT
        "ふ菓子", "甘味", 10, 20
    UNION ALL
    SELECT
        "ガム", "甘味", 20, 30
    UNION ALL
    SELECT
        "ポテトチップス", "スナック", 30, 60
    UNION ALL
    SELECT
        "カツ", "スナック", 15, 20
    UNION ALL
    SELECT
        "ガム", "スナック", 15, 30
),
budgets AS (
    SELECT
        "フルーツ" AS item_type, 70 AS budget
    UNION ALL
    SELECT
        "甘味", 50
    UNION ALL
    SELECT
        "スナック", 60
),
add_cpa AS (
    SELECT
        item
        , item_weight
        , item_type
        , price
        , ROW_NUMBER() OVER (PARTITION BY item_type ORDER BY item_weight/price DESC, price ASC) AS cpa_rank
    FROM
        items
),
add_stack_weight AS (
    SELECT
        *
        , SUM(price) OVER (PARTITION BY item_type ORDER BY cpa_rank ASC) AS stack_price
    FROM
        add_cpa
)
SELECT
    add_stack_weight.*
    , budgets.budget
FROM
    add_stack_weight
INNER JOIN budgets
    ON
       add_stack_weight.item_type = budgets.item_type
WHERE
    add_stack_weight.stack_price <= budgets.budget

질의 결과

아래와 같다.item_'과일'이 된 것은 딸기와 키위가 최적의 해결책이었으나 이번 시행으로 성가가 가장 좋은 바나나를 선택했다.
item
item_weight
item_type
price
cpa_rank
stack_price
budget
돈까스
15
간식
20
1
20
60
껌.
15
간식
30
2
50
60
• 바나나
150
과일.
50
1
50
70
초콜릿 쵸콜렛
40
단맛
30
1
30
50

결론

SQL로 탐욕법을 실시했다.분할 조합의 최적화 표를 만들 때 옵션을 선택하면 좋겠다.