You need to enable JavaScript to run this app. Python实现固定元素数量的0-1背包 改造代码为必选k个元素求助
优惠活动
大模型
产品
解决方案
定价
更多

Python实现固定元素数量的0-1背包 改造代码为必选k个元素求助

恰好选取k个元素的三维0-1背包改造

原代码的偏差来源

你当前代码输出“最多选k个”的最大价值,本质是DP数组全0初始化带来的逻辑偏差:全0的默认值等价于把“无论选几个物品,只要不超过k个,基础价值为0”作为合法状态,最终的转移结果自然不会强制凑够恰好k个物品。
要实现恰好选取的逻辑,必须区分可达合法状态和不可达状态,不能用0填充所有未初始化的位置。

具体改造步骤

  • 调整初始化逻辑:将dp数组的默认值设为代表不可达的负无穷,仅保留唯一合法初始边界:dp[0][y][x] = 0(即遍历前y个物品,恰好选0个时,无论剩余容量多少,价值都为0)。其余z>0的状态初始为不可达值,避免被错误计入最大值计算。
  • 状态转移逻辑保留原方向:原有的转移分支不需要大改,只需要确保仅从可达的状态中计算最大值:
    1. 不选当前第y个物品时,状态值继承dp[z][y-1][x](前y-1个物品恰好选z个、容量x下的最大价值)
    2. 选当前第y个物品时,需满足物品权重不超过剩余容量x,状态值取dp[z-1][y-1][x - weights[y-1]] + values[y-1](前y-1个物品恰好选z-1个,剩余容量装下第y个物品的总价值)
  • 修复回溯逻辑的现存bug:
    1. 原代码中dp=m的变量未定义,需将计算得到的完整dp数组传入回溯流程
    2. 原选中判断的逻辑错位:正确判断方式是对比当前状态值与“选入当前物品”的转移值,而非做差值计算
    3. 原代码中更新剩余容量的位置错误,先减物品索引再取权重会拿到错误的物品重量
    4. 回溯过程需要同步更新已选数量、剩余容量、遍历到的物品索引三个维度的指针,不能仅更新两个维度

可直接运行的实现代码

def knapsack_exact_k(n, max_weight, k, values, weights):
    # 用负无穷标记不可达状态
    INF = float('-inf')
    dp = [[[INF] * (max_weight + 1) for _ in range(n + 1)] for _ in range(k + 1)]
    # 初始化合法边界:恰好选0个物品时,任意容量下价值为0
    for y in range(n + 1):
        for x in range(max_weight + 1):
            dp[0][y][x] = 0

    for z in range(1, k + 1):
        for y in range(1, n + 1):
            for x in range(max_weight + 1):
                # 分支1:不选当前物品
                dp[z][y][x] = dp[z][y - 1][x]
                # 分支2:选当前物品(满足容量要求时计算)
                if weights[y - 1] <= x:
                    candidate = dp[z - 1][y - 1][x - weights[y - 1]] + values[y - 1]
                    if candidate > dp[z][y][x]:
                        dp[z][y][x] = candidate
    return dp

# 测试用例
if __name__ == "__main__":
    max_w = 10
    k = 4
    values = [1, 2, 3, 2, 2]
    weights = [4, 5, 1, 1, 1]
    n = len(values)
    dp = knapsack_exact_k(n, max_w, k, values, weights)
    max_value = dp[k][n][max_w]
    print(f"恰好选取{k}个物品的最大总价值:{max_value}")

    # 回溯提取选中物品(编号从1开始计数)
    selected = []
    cur_z, cur_y, cur_x = k, n, max_w
    while cur_y > 0 and cur_z > 0:
        # 判断当前物品是否被选入
        if weights[cur_y - 1] <= cur_x and dp[cur_z][cur_y][cur_x] == dp[cur_z - 1][cur_y - 1][cur_x - weights[cur_y - 1]] + values[cur_y - 1]:
            selected.append(cur_y)
            cur_z -= 1
            cur_x -= weights[cur_y - 1]
        cur_y -= 1
    print(f"选中的物品列表:{sorted(selected)}")

测试运行结果

用提供的测试数据运行,最终恰好选4个物品的最大价值为9,对应选中的物品为2、3、4、5,总重量为8,符合容量要求。

内容的提问来源于stack exchange,提问作者acidsyzygy

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.11.04 16:06:06