基于占比约束筛选N个箱子集合的算法求解

问题归类 #

这个问题属于约束满足问题(Constraint Satisfaction Problem, CSP)，同时归为组合优化领域的选择性约束问题。它和经典背包问题的核心差异在于：背包问题以最大化/最小化价值为核心目标，而你的需求是找到满足多维度比例约束、硬属性约束的可行子集——若后续无额外优化目标，核心是约束满足；若有优化需求（如最小化成本），则属于带约束的背包变种。

核心预处理步骤 #

首先处理硬约束：先从M个箱子中过滤出所有高度为20英寸的箱子，得到候选池M'。后续所有筛选操作都基于M'进行，问题简化为从M'中选出N个箱子，满足：

• 蓝色箱子占比20%-80%（即数量范围为 ceil(N*0.2) 到 floor(N*0.8)）
• 宽度20英寸的箱子占比5%-30%（即数量范围为 ceil(N*0.05) 到 floor(N*0.3)）

可行解求解算法 #

1. 贪心算法（快速获取任意可行解） #

适合只需要找到一个满足约束的集合的场景，步骤如下：

• 将候选池按属性分为4组：
  • A组：蓝色且宽度20英寸
  • B组：蓝色且宽度非20英寸
  • C组：非蓝色且宽度20英寸
  • D组：非蓝色且宽度非20英寸
• 计算各约束的数量上下限：
  • 蓝色总数量范围：blue_min = ceil(N*0.2)，blue_max = floor(N*0.8)
  • 宽20总数量范围：width20_min = ceil(N*0.05)，width20_max = floor(N*0.3)
• 优先选取A组箱子，这类箱子可同时贡献两个约束的计数，选取数量为 min(|A|, blue_min, width20_min)；
• 补充B组箱子，直到蓝色总数量达到blue_min（若B组数量不足，则直接判定无解）；
• 补充C组箱子，直到宽20总数量达到width20_min（若C组数量不足，则判定无解）；
• 用D组箱子填充剩余名额，同时确保蓝色总数量不超过blue_max、宽20总数量不超过width20_max；
• 若填充后总数量刚好为N，且所有约束都满足，则得到可行解。

2. 回溯枚举（精确获取所有可行解） #

如果需要枚举所有满足约束的集合，或贪心算法无法找到可行解时使用：

• 设从A、B、C、D组分别选取x、y、z、w个箱子，需满足：
  1. x + y + z + w = N
  2. blue_min ≤ x + y ≤ blue_max
  3. width20_min ≤ x + z ≤ width20_max
  4. x ≤ |A|, y ≤ |B|, z ≤ |C|, w ≤ |D|
• 遍历所有满足上述条件的(x,y,z,w)整数组合，对每个有效组合，从对应组中选取对应数量的箱子，即可得到一个可行集合。

带优化目标的算法（若后续有需求） #

如果需要在满足约束的前提下优化某个目标（如总采购成本最低、总容积最大），则属于带约束的0-1背包问题，可采用动态规划求解：

• 状态定义：dp[i][b][w] 表示前i个箱子中，选取了b个蓝色、w个宽20英寸的箱子时的最优目标值（如最小成本）；
• 状态转移：对每个箱子，根据其属性（是否蓝色、是否宽20），更新对应的状态值；
• 最终在所有满足 b ∈ [blue_min, blue_max]、w ∈ [width20_min, width20_max]、b + w - x = N（x为同时满足两个属性的箱子数，避免重复计数）的状态中，找到总数量为N的最优解。

内容的提问来源于stack exchange，提问作者Mike R