MySQL中如何求和并标记最接近月度最高津贴限额的对应数据行

这个需求本质是分组求解0-1背包问题，每个kids_id+date为独立分组，分组的背包容量为monthly_max_allowance，物品为分组内的每条津贴记录，重量与价值均为allowance，目标是找到总价值不超过容量的最大值对应物品集合。根据数据规模和精度要求可以选以下两种方案：

方案1：贪心算法（适配大数据量，SQL可直接实现，性能最优） #

如果业务允许优先选择金额更高的津贴记录凑额度（你提供的示例数据完全符合该规则的输出结果），可以直接用窗口函数累加实现，时间复杂度为O(n log n)，支持千万级数据批量运行：

验证查询SQL #

WITH ranked_records AS (
    SELECT 
        *,
        -- 同分组内按金额降序排序，金额相同则按转账日期升序优先选更早的记录
        SUM(allowance) OVER (
            PARTITION BY kids_id, date 
            ORDER BY allowance DESC, money_transfer_date ASC
            ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
        ) AS running_total
    FROM 你的表名
)
SELECT 
    kids_id, date, allowance, money_transfer_date, monthly_max_allowance,
    CASE WHEN running_total <= monthly_max_allowance THEN 1 ELSE 0 END AS calculated_to_keep
FROM ranked_records;

表更新SQL #

UPDATE 你的表名 t1
JOIN (
    SELECT 
        kids_id, date, money_transfer_date,
        CASE WHEN SUM(allowance) OVER (
            PARTITION BY kids_id, date 
            ORDER BY allowance DESC, money_transfer_date ASC
            ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
        ) <= monthly_max_allowance THEN 1 ELSE 0 END AS new_to_keep
    FROM 你的表名
) t2 ON t1.kids_id = t2.kids_id 
    AND t1.date = t2.date 
    AND t1.money_transfer_date = t2.money_transfer_date
SET t1.to_keep = t2.new_to_keep;

方案2：动态规划精确解（适用于单分组记录数≤15的场景，结果100%符合要求） #

如果必须枚举所有组合得到完全精确的最优解，纯SQL无法高效处理组合爆炸问题，建议用外部脚本批量处理，以下是Python实现示例：

import pandas as pd
import pymysql

# 数据库连接配置
conn = pymysql.connect(
    host="你的数据库地址",
    user="用户名",
    password="密码",
    database="库名"
)
cursor = conn.cursor()

# 先重置所有to_keep为0
cursor.execute("UPDATE 你的表名 SET to_keep = 0")
conn.commit()

# 获取所有独立分组
groups = pd.read_sql("SELECT DISTINCT kids_id, date, monthly_max_allowance FROM 你的表名", conn)

for _, group in groups.iterrows():
    kid_id = group['kids_id']
    stat_date = group['date']
    max_allowance = group['monthly_max_allowance']
    # 获取当前分组所有记录
    records = pd.read_sql(
        f"SELECT id, allowance FROM 你的表名 WHERE kids_id = {kid_id} AND date = {stat_date}", 
        conn
    )
    n = len(records)
    if n == 0:
        continue
    # 0-1背包动态规划
    dp = [0] * (max_allowance + 1)
    # 记录最优组合的id列表
    best_ids = [[] for _ in range(max_allowance + 1)]
    
    for idx, row in records.iterrows():
        allow = row['allowance']
        rec_id = row['id']
        # 倒序遍历避免重复选
        for j in range(max_allowance, allow - 1, -1):
            if dp[j - allow] + allow > dp[j]:
                dp[j] = dp[j - allow] + allow
                best_ids[j] = best_ids[j - allow] + [rec_id]
    # 找到最大的不超过限额的总和
    max_sum = max(dp)
    target_ids = best_ids[dp.index(max_sum)]
    if target_ids:
        # 批量更新标记
        id_str = ','.join(map(str, target_ids))
        cursor.execute(f"UPDATE 你的表名 SET to_keep = 1 WHERE id IN ({id_str})")
        conn.commit()

cursor.close()
conn.close()

内容的提问来源于stack exchange，提问作者James Miller