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的状态初始为不可达值,避免被错误计入最大值计算。 - 状态转移逻辑保留原方向:原有的转移分支不需要大改,只需要确保仅从可达的状态中计算最大值:
- 不选当前第y个物品时,状态值继承
dp[z][y-1][x](前y-1个物品恰好选z个、容量x下的最大价值) - 选当前第y个物品时,需满足物品权重不超过剩余容量x,状态值取
dp[z-1][y-1][x - weights[y-1]] + values[y-1](前y-1个物品恰好选z-1个,剩余容量装下第y个物品的总价值)
- 不选当前第y个物品时,状态值继承
- 修复回溯逻辑的现存bug:
- 原代码中
dp=m的变量未定义,需将计算得到的完整dp数组传入回溯流程 - 原选中判断的逻辑错位:正确判断方式是对比当前状态值与“选入当前物品”的转移值,而非做差值计算
- 原代码中更新剩余容量的位置错误,先减物品索引再取权重会拿到错误的物品重量
- 回溯过程需要同步更新已选数量、剩余容量、遍历到的物品索引三个维度的指针,不能仅更新两个维度
- 原代码中
可直接运行的实现代码
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
相关产品推荐
相关产品推荐

