双背包问题：两个工厂时长限制下可生产的最大不同物品数量求解

核心思路 #

要最大化生产的物品数量，优先选择耗时最短的物品是最优策略——相同数量下，总耗时越小，越容易分配到两个工厂的可用时长中。基于这个特性，我们可以用「排序+二分查找+01背包校验」的方案把时间复杂度降到可接受范围。

注意不能只通过前k个物品总耗时≤X+Y来判定可行，举个反例：X=3，Y=3，物品耗时为[2,2,2]，总耗时6=3+3，但最多只能生产2个物品，因为每个工厂最多放1个耗时2的物品，所以必须额外校验分配可行性。

具体实现步骤 #

• 第一步：将数组A从小到大排序，计算前缀和数组pre_sum，其中pre_sum[k]表示前k个物品的总耗时。
• 第二步：二分查找最大的可行物品数k，查找范围是0~min(N, X+Y)（因为每个物品至少耗时1，最多不可能超过两个工厂总时长）。
• 第三步：对每个二分的中间值mid做可行性校验：
  1. 如果pre_sum[mid] > X + Y，总耗时超过两个工厂总时长，直接判定不可行，缩小二分上界。
  2. 否则我们需要验证：前mid个物品中能否选出一个子集放到第一个工厂，满足子集耗时s符合条件 max(0, pre_sum[mid] - Y) ≤ s ≤ X。这个条件等价于剩下的物品总耗时pre_sum[mid]-s不超过第二个工厂的时长Y。
  3. 用01背包计算前mid个物品能凑出的所有≤X的耗时，只要存在符合上述区间的s，就判定mid可行，扩大二分下界。

复杂度分析 #

• 排序复杂度：O(N logN)
• 二分次数最多为log(1000) ≈ 10次
• 每次校验的01背包复杂度为O(mid * X)，mid最大为1000，X最大为500
• 总计算量约为10 * 1000 * 500 = 5 * 10^6，远低于超时阈值，完全满足性能要求。

示例验证 #

拿示例2验证：
A = [6,5,5,4,3]排序后为[3,4,5,5,6]，X=8，Y=9。
当校验mid=4时，pre_sum[4] = 3+4+5+5 = 17 = X+Y，需要s满足17-9=8 ≤ s ≤ 8，即s=8。前4个物品可以凑出3+5=8，符合条件，所以mid=4可行。
当mid=5时，pre_sum[5] = 23 > 17，直接不可行，最终答案为4，和示例一致。

伪代码参考 #

# 输入：A数组，X，Y
A.sort()
n = len(A)
pre_sum = [0]*(n+1)
for i in range(n):
    pre_sum[i+1] = pre_sum[i] + A[i]

left = 0
right = min(n, X+Y)
ans = 0
while left <= right:
    mid = (left + right) // 2
    if pre_sum[mid] > X + Y:
        right = mid - 1
        continue
    # 01背包求能凑出的<=X的和
    dp = [False]*(X+1)
    dp[0] = True
    for i in range(mid):
        num = A[i]
        for j in range(X, num-1, -1):
            if dp[j - num]:
                dp[j] = True
    # 检查有没有符合区间的s
    lower = max(0, pre_sum[mid] - Y)
    valid = False
    for s in range(lower, X+1):
        if dp[s]:
            valid = True
            break
    if valid:
        ans = mid
        left = mid + 1
    else:
        right = mid - 1
print(ans)

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