印刷贴纸印版数量最小化算法设计技术求助

问题描述 #

某印刷企业需印刷X种不同类型的贴纸，每种贴纸对应明确需求量。每个印版可容纳N个贴纸位置，且印版可重复用于印刷多张纸张。由于印版设计开发成本远高于纸张成本，核心目标是最小化所需的独特印版数量。

示例说明 #

当印版容量N=10，贴纸需求为{A:200, B:300}时：

• 非优化方案：制作2个印版，一个全为A贴纸（10个）印刷20张，一个全为B贴纸（10个）印刷30张，总印版数为2。
• 优化方案：制作1个印版，包含4个A贴纸和6个B贴纸，印刷50张即可满足所有需求，总印版数为1。

When plate size = 10 and required quantities = {A: 200, B: 300}

Unoptimized Approach:

 _________               _________
|A|A|A|A|A| x 20        |B|B|B|B|B| x 30
|A|A|A|A|A|             |B|B|B|B|B|
 ---------               ---------

Optimized Approach:
 _________
|A|A|A|A|B| x 50
|B|B|B|B|B|
 ---------

现有尝试的局限 #

曾采用暴力法：按需求量排序贴纸，计算比例后分配印版位置，印刷至最小需求量耗尽（允许少量浪费），但该方法无法保证得到最优解。通用背包问题解法不匹配此问题的核心目标，需针对性方案。

解决方案思路与算法 #

问题本质建模 #

该问题属于整数配比优化问题，核心是找到最少的印版类型，使得通过重复印刷这些印版的纸张，能覆盖所有贴纸的需求量：

• 设贴纸集合为 ( S = {s_1, s_2, ..., s_X} )，对应需求量 ( D = {d_1, d_2, ..., d_X} )
• 每个印版是向量 ( P = {p_1, p_2, ..., p_X} )，其中 ( p_i ) 为印版中贴纸 ( s_i ) 的数量，满足 ( \sum_{i=1}^X p_i = N )（( p_i ) 为非负整数）
• 每个印版 ( P_j ) 对应印刷次数 ( k_j )，需满足 ( \sum_{j} p_{j,i} \times k_j \geq d_i )（所有贴纸需求被覆盖）
• 目标：最小化印版类型的数量

具体算法步骤 #

1. 优先验证单印版可行性（最优情况）

先判断是否能用1个印版解决问题：

• 计算各贴纸需求占总需求的比例：( r_i = \frac{d_i}{\sum_{i} d_i} )
• 按比例分配印版位置：( p_i = \text{round}(r_i \times N) )，调整数值使 ( \sum p_i = N )（优先调整比例误差最大的项）
• 计算所需印刷次数 ( k = \max\left( \lceil \frac{d_i}{p_i} \rceil \right) )（跳过 ( p_i=0 ) 的贴纸）
• 验证 ( p_i \times k \geq d_i ) 对所有贴纸成立，若成立则1个印版即可满足需求（如示例场景）

2. 多印版迭代贪心优化

若单印版不可行，按以下步骤生成印版：

• 步骤1：选择当前需求量最大的贴纸 ( s_m )，创建印版时尽可能多容纳该贴纸（可结合其他高需求贴纸配比），计算所需印刷次数 ( k = \lceil \frac{d_m}{p_m} \rceil )，更新剩余需求量 ( d_i' = \max(d_i - p_i \times k, 0) )
• 步骤2：对剩余需求量重复上述过程，直到所有需求量为0
• 步骤3：合并优化印版集合：检查是否有两个印版可合并为一个，调整后仍能通过对应印刷次数满足需求，减少印版数量

3. 整数线性规划求解（精确最优解）

若需要绝对最优解，可构建整数线性规划模型，用专业求解器（如PuLP、CPLEX）求解：

• 变量：
  • ( x_{j,i} )：第j个印版中贴纸i的数量（非负整数）
  • ( k_j )：第j个印版的印刷次数（正整数）
  • ( y_j )：0-1变量，标记是否使用第j个印版
• 约束：
  1. ( \sum_{i} x_{j,i} = N \times y_j )（印版容量约束）
  2. ( \sum_{j} x_{j,i} \times k_j \geq d_i )（需求覆盖约束）
  3. ( x_{j,i} \leq N \times y_j )（未使用的印版无贴纸）
• 目标：最小化 ( \sum_{j} y_j )

注意事项 #

• 暴力法的比例分配忽略整数约束，易导致需求无法覆盖，需调整印版配比后验证
• 允许少量浪费时，可适当调整印版内贴纸数量，避免因过度追求精确比例增加印版数量
• 贴纸类型较多时，单印版大概率不可行，需依赖迭代贪心或整数规划方案

内容的提问来源于stack exchange，提问作者Huzaifa Imran