如何通过Karp归约将疫苗分配问题转化为子集和问题证明其NP完全性

首先澄清归约方向：要证明问题是NP完全，需要将已知NP完全的子集和问题归约到待证明的疫苗分配问题；如果是要将疫苗分配问题转为子集和问题求解，归约方向相反，两种场景的实现逻辑分别说明如下。

一、证明疫苗分配问题属于NP类 #

任意候选解都可以在多项式时间内验证合法性：

• 对每个年龄组k，检查接种人数x_k ≥ ⌈(t_k/100)*a_k⌉，满足最低接种率要求
• 计算总疫苗消耗量total = Σ(x_k*d_k)，检查total ≤ D（不超过总疫苗量）且D - total ≤ S（剩余疫苗不超过上限）
  所有检查步骤时间复杂度为O(n)，因此该问题属于NP类。

二、子集和到疫苗分配的Karp归约（证明NP难） #

通过该归约可证明疫苗分配问题是NP完全，构造逻辑如下：

归约规则 #

给定任意子集和实例：正整数集合W={w_1,w_2,...,w_n}，目标和K，我们构造等价的疫苗分配实例：

• 总疫苗剂量D = K
• 共设置n个年龄组，每个年龄组k对应子集和的元素w_k：
  • 年龄组k总人数a_k = 1
  • 单人完全接种所需剂量d_k = w_k
  • 最低接种率t_k = 0%（即可选0或1人接种，对应子集是否选中w_k）
• 剩余疫苗上限S = 0（要求消耗疫苗恰好等于总剂量D）

等价性证明 #

• 若子集和有解：选中的元素和为K，对应选中的年龄组各接种1人，其余接种0人。所有年龄组满足接种率要求，总消耗为K=D，剩余疫苗为0≤S，因此疫苗分配实例有解。
• 若疫苗分配有解：总消耗恰好为D=K，每个年龄组接种人数只能是0或1，选接种1人的年龄组对应的w_k组成的子集和恰好为K，因此子集和实例有解。
  整个构造过程时间复杂度为O(n)，符合Karp归约的多项式时间要求。

三、疫苗分配到子集和的归约（用于求解） #

如果需要将疫苗分配问题转为标准子集和问题求解，构造逻辑如下：

1. 先计算每个年龄组的最低接种人数min_k = ⌈(t_k/100)*a_k⌉，计算最低总消耗base_consume = Σ(min_k*d_k)，如果base_consume > D直接判定无解。
2. 计算额外分配的疫苗区间：剩余疫苗要求≤S，即总消耗≥D-S，因此额外分配的疫苗量X需要满足extra_low ≤ X ≤ extra_high，其中：
   • extra_low = max(0, (D - S) - base_consume)
   • extra_high = D - base_consume
     如果extra_low > extra_high直接判定无解。
3. 对每个年龄组k，生成(a_k - min_k)个大小为d_k的元素，对应给该年龄组额外多接种1人的疫苗消耗。
4. 转为标准子集和问题：添加辅助元素M = extra_high + 1，子集和目标值设为extra_high + extra_low，只要该子集和实例有解，原疫苗分配问题就有解。

等价性证明：辅助元素M大于所有额外元素的最大可能和，因此目标和只能由M + 大小为extra_low的子集组成，恰好对应额外分配量落在要求区间内的条件。

四、伪代码实现 #

# 疫苗分配实例转子集和实例
def vaccine_to_subset_sum(D: int, n: int, a_list: list, d_list: list, t_list: list, S: int):
    # 计算每个年龄组最低接种人数
    min_x = [ceil((t_k / 100) * a_k) for a_k, t_k in zip(a_list, t_list)]
    base_consume = sum(x * d_k for x, d_k in zip(min_x, d_list))
    # 最低需求超过总疫苗量，无解
    if base_consume > D:
        return None
    # 计算额外分配的可行区间
    extra_low = max(0, (D - S) - base_consume)
    extra_high = D - base_consume
    if extra_low > extra_high:
        return None
    # 生成额外分配的元素集合
    extra_elements = []
    # 可选：维护元素到年龄组的映射，方便后续反向解析解
    elem_to_group = []
    for k in range(n):
        add_cnt = a_list[k] - min_x[k]
        extra_elements.extend([d_list[k]] * add_cnt)
        elem_to_group.extend([k] * add_cnt)
    # 构造标准子集和实例
    M = extra_high + 1
    target = extra_high + extra_low
    subset_sum_elements = extra_elements + [M]
    return (subset_sum_elements, target, min_x, elem_to_group)

# 子集和解反向转换为疫苗分配解
def subset_sol_to_vaccine_sol(sol_indices: list, min_x: list, elem_to_group: list):
    x = min_x.copy()
    m_idx = len(elem_to_group)
    for idx in sol_indices:
        if idx == m_idx:
            continue
        group = elem_to_group[idx]
        x[group] += 1
    return x

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