背包问题是动态规划中的经典问题类型，也是面试和竞赛中的高频考点。本文将系统讲解如何识别背包问题、通用的解题套路，并以 LeetCode 474「一和零」为例深入剖析。

一、如何识别背包问题

当你遇到以下特征的题目时，很可能是背包问题：

1.1 核心特征

问题描述中包含以下要素：

• 物品集合：有一组可选的物品（数组、列表等）
• 容量限制：存在一个或多个限制条件（重量、体积、数量等）
• 价值/目标：需要优化某个目标（最大价值、最小代价、方案数等）
• 选择约束：每个物品有选择次数的限制（选一次、无限次、至多 k 次等）

1.2 常见问法

背包问题通常以以下形式出现：

• “在限制 X 的情况下，最多/最少能…”
• “选择若干物品，使得总和不超过…”
• “有多少种方法可以…”
• “能否恰好达到…”

1.3 背包问题的分类

根据物品的选择规则和目标函数，背包问题分为：

类型	特点	典型问题
0-1 背包	每个物品只能选择 0 次或 1 次	「分割等和子集」
完全背包	每个物品可以选择无限次	「零钱兑换」
多重背包	每个物品可以选择有限次	「多重背包问题」
多维背包	有多个容量限制维度	「一和零」(本题)
分组背包	物品分组，每组只能选一个	「分组背包问题」

阅读全文»

一份全面的微服务架构参考手册，系统梳理 29 个核心概念，涵盖基础架构、可靠性保障、配置治理、可观测性、安全认证、数据管理、部署运维和高级模式等八大领域。每个概念都配有原理图解、实战代码和工具对比，适合作为日常开发的技术速查和架构设计的参考指南。

目录

基础架构层

• 1. 服务拆分（Service Decomposition）
• 2. API 网关（API Gateway）
• 3. RPC 与服务间通信（RPC & Inter-Service Communication）

可靠性保障

• 4. 熔断（Circuit Breaker）
• 5. 服务降级（Service Degradation）
• 6. 重试与超时（Retry & Timeout）
• 7. 隔离（Isolation）
• 8. 限流（Rate Limiting）

配置与治理

• 9. 服务发现与注册（Service Discovery & Registration）
• 10. 配置中心（Configuration Center）
• 11. 负载均衡（Load Balancing）
• 12. 服务网格（Service Mesh）

可观测性

• 13. 链路追踪（Distributed Tracing）
• 14. 日志聚合（Log Aggregation）
• 15. 监控告警（Monitoring & Alerting）
• 16. 健康检查（Health Check）

安全与认证

• 17. 认证与授权（Authentication & Authorization）
• 18. API 安全（API Security）
• 19. 服务间认证（Service-to-Service Auth）

数据管理

• 20. 分布式事务（Distributed Transaction）
• 21. 分布式缓存（Distributed Cache）
• 22. 数据一致性（Data Consistency）
• 23. 数据库分片（Database Sharding）

部署与运维

• 24. 容器化（Containerization）
• 25. CI/CD
• 26. 灰度发布（Canary Deployment）

高级模式

• 27. 事件驱动架构（Event-Driven Architecture）
• 28. BFF 模式（Backend for Frontend）
• 29. 领域驱动设计（DDD in Microservices）

阅读全文»

权限系统设计：从 RBAC 到图权限，再到列表查询的性能难题

一、权限系统的本质

权限系统的核心是三元组：实体、资源、操作

以 Linux 文件系统为例：

• 实体（Who）: 用户（User）
• 资源（What）: 文件（File）
• 操作（How）: rwx（读、写、执行）

# 示例：用户 alice 对文件 /data/report.txt 有读写权限
alice (实体) -> /data/report.txt (资源) -> rw- (操作)

二、权限模型的演进

2.1 ACL（访问控制列表）- 最原始的方式

直接定义 “谁对什么有什么权限”：

alice   -> /data/report.txt  -> read, write
bob     -> /data/report.txt  -> read
charlie -> /data/secret.txt  -> read, write

问题：

• 用户多了管理困难（每个用户都要单独配置）
• 权限变更成本高（要改 100 个用户的权限就要改 100 次）

2.2 用户组（Group）- 对实体的包装

引入"组"的概念，批量管理用户：

组: managers = [alice, bob, charlie]
组: developers = [david, eve, frank]

managers    -> /data/reports/*  -> read, write
developers  -> /data/code/*     -> read, write, execute

改进：

• 新增用户只需加入组
• 调整组的权限即可影响所有成员

仍然不够：权限类型（read, write, execute）仍然散落各处，难以复用

2.3 RBAC（基于角色的访问控制）- 对操作的包装

引入"角色"的概念，封装一组操作：

角色定义:
  - 角色: admin        -> 操作: [read, write, delete, grant]
  - 角色: editor       -> 操作: [read, write]
  - 角色: viewer       -> 操作: [read]

用户分配:
  - alice   -> 角色: admin    (on /data/reports/*)
  - bob     -> 角色: editor   (on /data/reports/*)
  - charlie -> 角色: viewer   (on /data/reports/*)

优点：

• 权限管理清晰：用户 -> 角色 -> 资源
• 易于扩展：新增角色即可，无需修改用户配置
• Go 语言推荐库：Casbin (支持 RBAC/ABAC/RESTful 等多种模型)

2.4 RBAC 的局限性

RBAC 适合：

• ✅ 静态的组织结构（角色相对固定）
• ✅ 权限与角色强相关（如：管理员、编辑、访客）
• ✅ 资源类型有限（如：文档、订单、用户）

RBAC 不适合：

• ❌ 动态的权限继承（领导自动继承下属权限）
• ❌ 复杂的关系链（A 的上级的上级也有权限）
• ❌ 资源之间有依赖（文件夹权限影响子文件）

三、权限继承的难题：Google Zanzibar

3.1 真实场景：组织层级权限

场景:
  - Alice 是 Bob 的领导
  - Bob 对资源 C 有权限
  - 期望: Alice 自动继承 Bob 的权限（领导能看下属的所有资源）

传统 RBAC 解决不了这个问题，因为：

• Bob 的权限可能很多，手动给 Alice 分配不现实
• Bob 的下属可能变化（离职、调岗），需要实时更新
• 权限是间接的、传递的

阅读全文»

一、什么是"最大化最小值"问题？

在算法题中，经常会遇到这样的描述：

• “让所有工人的最大工作量尽可能小”
• “让所有城市的最小电量尽可能大”
• “让木材切割后的最小长度尽可能大”
• “让学生分配到的最大任务数尽可能小”

这类问题有个共同特点：求在某种约束条件下，某个极值指标的最优值。

乍一看这类问题很难直接求解，但有一个巧妙的思路：把"求最优值"转换为"判断某个值是否可行"。

---

二、核心思想：二分答案法

2.1 为什么要二分答案？

直接思路的困境：
假设要求"分配任务后，学生们的最大任务量的最小值"，如果直接枚举所有可能的分配方案，复杂度会是指数级的，根本无法接受。

转换思路：
我们换个角度问问题：

• 原问题：“最优答案是多少？”（不知道怎么求）
• 新问题：“答案能否达到 X？”（相对容易判断）

如果能高效判断"答案是否能达到 X"，那我们就可以用二分搜索在所有可能的答案中找到最优的那个！

2.2 为什么二分法有效？关键在于单调性

二分答案法之所以可行，是因为这类问题有一个关键性质：单调性。

以"最大化最小值"为例：

• 如果"让所有城市电量都达到 10"可以实现，那么"让所有城市电量都达到 9、8、7…"肯定也可以实现（要求更低了）
• 如果"让所有城市电量都达到 10"无法实现，那么"让所有城市电量都达到 11、12、13…"肯定也无法实现（要求更高了）

这种单调性意味着：存在一个临界值 M，小于等于 M 的都可以实现，大于 M 的都无法实现。

答案值:  0   1   2   3   4   5   6   7   8   9   10  11  12
是否可行: ✓   ✓   ✓   ✓   ✓   ✓   ✓   ✓   ✗   ✗   ✗   ✗   ✗
                                      ↑
                                   我们要找的最优答案

这正是二分搜索的应用场景！我们要找的就是那个"从可行到不可行"的临界点。

---

三、解题框架（四步走）

第一步：识别问题类型

看到以下关键词就要想到二分答案法：

• “最大化最小值”
• “最小化最大值”
• “在…约束下，求…的最优值”
• “让…尽可能大/小”

第二步：确定二分搜索范围

需要确定答案的可能范围 [left, right]：

• left（最小可能值）：通常是理论最小值，比如 0，或者初始状态下已有的最小值
• right（最大可能值）：通常是理论最大值，比如所有资源之和，或者题目给定的上限

第三步：设计 check(mid) 函数

这是最关键的一步！

check(mid) 函数的作用：判断答案能否达到 mid。

• 返回 true：说明 mid 这个答案可以实现，真正的最优答案 ≥ mid
• 返回 false：说明 mid 这个答案无法实现，真正的最优答案 < mid

设计 check 函数时，通常会用到贪心、滑动窗口、差分数组等技巧。

第四步：二分搜索主循环

def solve():
    left, right = 确定搜索范围
    
    while left < right:
        mid = (left + right + 1) // 2  # 对于"最大化最小值"问题
        
        if check(mid):  # mid 可行
            left = mid  # 尝试更大的值
        else:  # mid 不可行
            right = mid - 1  # 尝试更小的值
    
    return left  # 最终 left == right，就是答案

注意：

• "最大化最小值"问题：mid = (left + right + 1) // 2，可行时 left = mid
• "最小化最大值"问题：mid = (left + right) // 2，可行时 right = mid

---

阅读全文»

前言

Gin 是 Go 语言中最流行的 Web 框架之一，以其出色的性能和简洁的 API 设计深受开发者喜爱。然而，从"能用"到"好用"之间，还有很多工程实践需要遵循。本文将分享我在实际项目中总结的 Gin 最佳实践，帮助你构建更加健壮、可维护的应用。

🚀 快速开始

本文所有最佳实践已整合成完整的项目模板，可直接使用：

GitHub 仓库: https://github.com/d60-Lab/gin-template

# 方式 1: 使用 GitHub 模板创建项目
# 访问 https://github.com/d60-Lab/gin-template
# 点击 "Use this template" 按钮

# 方式 2: 克隆仓库
git clone https://github.com/d60-Lab/gin-template.git my-project
cd my-project

# 方式 3: 使用初始化脚本（推荐）
curl -fsSL https://raw.githubusercontent.com/d60-Lab/gin-template/main/scripts/init-project.sh | bash -s -- my-project

模板特性：

• ✅ 完整的 DDD 分层架构
• ✅ Swagger API 文档
• ✅ 单元测试 + 集成测试
• ✅ OpenTelemetry 链路追踪
• ✅ Sentry 错误监控
• ✅ Pre-commit + golangci-lint
• ✅ GitHub Actions CI/CD
• ✅ REST Client 测试集合
• ✅ 开发工具配置齐全

详细使用说明请参考 README.md。

阅读全文»

高并发系统的设计本质上是一场资源与需求之间的博弈。当系统面临流量洪峰时,我们需要的不是单一的技术方案,而是一套系统性的思维框架。这个框架的核心可以概括为一句话:分层加缓存。但这句话背后,隐藏着无数需要权衡的技术决策。

阅读全文»