求高效算法：计算企业可服务的最大客户数量

问题定义 #

企业拥有n类产品，每类产品有固定可用库存；同时有c位客户，每位客户对每类产品有对应的订购量（可为0）。服务客户需满足其所有产品的订购需求，目标是找出可服务的最大客户数量。

示例输入数据 #

示例说明 #

可服务的最大客户数为2：

• 服务客户1：消耗30单位Type A、0单位Type B
• 服务客户3：消耗0单位Type A、10单位Type B

若选择服务客户2，会耗尽两类产品的所有库存，无法再服务其他客户，因此不是最优解。

暴力解法代码 #

暴力解法通过枚举所有客户组合，从最大可能的客户数开始检查，直到找到满足库存约束的组合。但这种方法时间复杂度为O(2^c)，客户数稍多就会耗时过长。

import pandas as pd
import itertools
 
def findsubsets(s, n):
    return list(itertools.combinations(s, n))
 
df = pd.read_excel('file.xls')

s = df.columns[4:-1]
l = len(s)

stock = df['Available Stock'][:-1]
max_fulfil = 0
ans = []
for i in range(l, -1, -1):
    combs = findsubsets(s, i)
    print(i)
    for comb in combs:
        order_stock = None
        for c in comb:
            if order_stock is None:
                order_stock = df[c][:-1].copy(deep=True)
            else:
                order_stock += df[c][:-1]
        if (sum(order_stock > stock) == 0):
            max_fulfil = i
            ans.append(comb)  # 修正原代码的空值append问题
    if max_fulfil != 0:
        break
print(ans)
print(max_fulfil)

更高效的解决方案 #

针对该问题，推荐两种高效优化思路，大幅降低时间复杂度：

1. 二分查找 + Meet-in-the-Middle 分治枚举 #

核心思路

• 二分答案：从客户总数c开始向下二分，判断是否存在k个客户的总需求不超过库存，找到最大的可行k。
• 分治枚举检查可行性：将客户分成两组，分别枚举每组所有子集的「客户数+总需求」信息，然后在两组间匹配互补子集，判断是否存在总数为k且总需求符合约束的组合。

该方法时间复杂度为O(2^{(c/2))，相比暴力枚举的O(2}c)，当c=40时，2^20≈1e6，完全可行。

代码实现

import pandas as pd

def get_subset_info(customers_demand):
    # 生成所有子集的（客户数，总需求）信息
    subset_info = []
    n = len(customers_demand)
    for mask in range(0, 1 << n):
        count = bin(mask).count('1')
        total_demand = [0] * len(customers_demand[0])
        for i in range(n):
            if mask & (1 << i):
                for j in range(len(total_demand)):
                    total_demand[j] += customers_demand[i][j]
        subset_info.append((count, total_demand))
    return subset_info

def is_possible(k, customers_demand, stock):
    if k == 0:
        return True
    # 将客户分成两组
    mid = len(customers_demand) // 2
    left = customers_demand[:mid]
    right = customers_demand[mid:]
    
    left_info = get_subset_info(left)
    right_info = get_subset_info(right)
    
    # 对右侧信息按客户数分组，便于快速查找
    right_groups = {}
    for cnt, demand in right_info:
        if cnt not in right_groups:
            right_groups[cnt] = []
        right_groups[cnt].append(demand)
    
    # 遍历左侧子集，匹配右侧互补子集
    for left_cnt, left_demand in left_info:
        needed = k - left_cnt
        if needed < 0 or needed not in right_groups:
            continue
        for right_demand in right_groups[needed]:
            valid = True
            for d1, d2, s in zip(left_demand, right_demand, stock):
                if d1 + d2 > s:
                    valid = False
                    break
            if valid:
                return True
    return False

def max_customers(df):
    # 提取库存和客户需求数据
    stock = df['Available Stock'][:-1].tolist()
    customer_cols = df.columns[4:-1]
    customers_demand = []
    for col in customer_cols:
        customers_demand.append(df[col][:-1].tolist())
    
    # 二分查找最大可行客户数
    left, right = 0, len(customers_demand)
    best = 0
    while left <= right:
        mid = (left + right) // 2
        if is_possible(mid, customers_demand, stock):
            best = mid
            left = mid + 1
        else:
            right = mid - 1
    return best

# 调用示例
df = pd.read_excel('file.xls')
print(max_customers(df))

2. 回溯剪枝法 #

核心思路

• 先将客户按总需求从小到大排序，优先选择需求小的客户，更快找到较大的可行客户数。
• 回溯过程中剪枝：
  1. 当前选中客户数 + 剩余未选客户数 ≤ 已找到的最大客户数，直接终止分支。
  2. 选中当前客户后总需求超过库存，跳过该客户。

该方法在客户数适中（c<=30）时效率较高，实现简单。

代码实现

import pandas as pd

def backtrack(index, current_count, current_demand, customers_demand, stock, max_count):
    if index == len(customers_demand):
        if current_count > max_count[0]:
            max_count[0] = current_count
        return
    # 剪枝：剩余客户数无法超越当前最优解，直接返回
    if current_count + (len(customers_demand) - index) <= max_count[0]:
        return
    
    # 不选当前客户
    backtrack(index + 1, current_count, current_demand.copy(), customers_demand, stock, max_count)
    
    # 选当前客户，检查库存约束
    new_demand = [current_demand[i] + customers_demand[index][i] for i in range(len(stock))]
    valid = True
    for d, s in zip(new_demand, stock):
        if d > s:
            valid = False
            break
    if valid:
        backtrack(index + 1, current_count + 1, new_demand, customers_demand, stock, max_count)

def max_customers_backtrack(df):
    stock = df['Available Stock'][:-1].tolist()
    customer_cols = df.columns[4:-1]
    customers_demand = []
    for col in customer_cols:
        customers_demand.append(df[col][:-1].tolist())
    
    # 按总需求从小到大排序，优先选需求小的客户
    customers_demand.sort(key=lambda x: sum(x))
    
    max_count = [0]
    backtrack(0, 0, [0]*len(stock), customers_demand, stock, max_count)
    return max_count[0]

# 调用示例
df = pd.read_excel('file.xls')
print(max_customers_backtrack(df))

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