指定每组选取固定数量物品的背包问题求解

这是0-1背包问题的一种分组约束变种：每个物品仅归属于一个分组，目标是在背包容量限制下最大化总收益，核心规则是每组必须恰好选取指定数量的物品。

它和多选择背包问题（Multiple Choice Knapsack Problem）类似，但后者每组仅需选1个物品，而本问题要求每组选取固定数量的物品（例如分组A必须选2个，最终解里该组物品数量必须恰好是2）。

问题要素 #

• 每个物品包含：价值、重量、所属分组
• 每个分组有明确的选取数量要求
• 存在背包最大容量约束

参数定义 #

• values[i] = 第i个物品的价值
• weights[i] = 第i个物品的重量
• groups[i] = 第i个物品所属分组
• C = 背包容量
• n = 物品总数
• m = 分组总数
• count[j] = 第j组需选取的物品数量

解决方案 #

1. 递归解法（适合小数据量）

递归思路：按分组依次处理，对当前分组枚举所有恰好选取count[j]个物品的组合，递归处理剩余分组，跟踪当前总重量和总价值，最终返回符合容量约束的最大价值。

def knapsack_recursive(values, weights, groups, count, C):
    # 按分组整理物品
    group_items = {}
    for idx, g in enumerate(groups):
        if g not in group_items:
            group_items[g] = []
        group_items[g].append((values[idx], weights[idx]))
    
    group_list = list(group_items.keys())
    required_counts = {g: count[g] for g in group_list}

    def helper(group_idx, current_weight, current_value):
        if group_idx == len(group_list):
            return current_value if current_weight <= C else -float('inf')
        
        current_group = group_list[group_idx]
        items = group_items[current_group]
        need = required_counts[current_group]
        max_val = -float('inf')

        # 枚举当前组选need个物品的所有组合
        from itertools import combinations
        for combo in combinations(items, need):
            total_w = sum(w for v, w in combo)
            total_v = sum(v for v, w in combo)
            if current_weight + total_w > C:
                continue
            res = helper(group_idx + 1, current_weight + total_w, current_value + total_v)
            if res > max_val:
                max_val = res
        
        return max_val
    
    result = helper(0, 0, 0)
    return result if result != -float('inf') else 0  # 无解返回0

2. 动态规划解法（高效处理大数据量）

DP思路：

1. 对每个分组，预处理出选取count[j]个物品时，不同重量对应的最大价值（即该组的"物品组合背包"）
2. 采用分层DP，将每个分组的预处理结果合并到全局DP数组中，最终得到容量C下的最大价值

def knapsack_dp(values, weights, groups, count, C):
    # 按分组整理物品
    group_items = {}
    for idx, g in enumerate(groups):
        if g not in group_items:
            group_items[g] = []
        group_items[g].append((values[idx], weights[idx]))
    
    group_list = list(group_items.keys())
    # 初始化DP：dp[w]表示当前总重量w时的最大价值
    dp = [-float('inf')] * (C + 1)
    dp[0] = 0  # 初始状态：重量0，价值0

    for g in group_list:
        items = group_items[g]
        need = count[g]
        # 预处理当前组选need个物品的所有可能重量-价值组合
        group_dp = [[-float('inf')] * (C + 1) for _ in range(need + 1)]
        group_dp[0][0] = 0
        for v, w in items:
            # 倒序遍历，避免重复选取
            for k in range(need, 0, -1):
                for weight in range(C, w - 1, -1):
                    if group_dp[k-1][weight - w] != -float('inf'):
                        group_dp[k][weight] = max(group_dp[k][weight], group_dp[k-1][weight - w] + v)
        
        # 提取当前组选need个物品的有效状态
        current_options = {}
        for weight in range(C + 1):
            if group_dp[need][weight] != -float('inf'):
                current_options[weight] = group_dp[need][weight]
        
        # 合并到全局DP
        new_dp = [-float('inf')] * (C + 1)
        for prev_w in range(C + 1):
            if dp[prev_w] == -float('inf'):
                continue
            for curr_w, curr_v in current_options.items():
                if prev_w + curr_w <= C:
                    new_dp[prev_w + curr_w] = max(new_dp[prev_w + curr_w], dp[prev_w] + curr_v)
        dp = new_dp
    
    # 取所有不超过C的重量中最大的价值，无解返回0
    max_val = max(dp)
    return max_val if max_val != -float('inf') else 0

内容的提问来源于stack exchange，提问作者Pablo Roldán