Java最小成本背包求解：修改代码以存储最优解并输出选中物品索引

现有代码实现的是总重量不低于指定minWeight值时的最低成本计算，仅能输出最终成本数值，缺少选中物品的存储逻辑。可通过新增路径标记数组、反向回溯的方式补全这一能力，具体调整如下：

核心调整思路 #

• 保留原有DP计算最小成本的核心逻辑，不改动状态转移的规则
• 新增boolean类型二维数组，维度为「物品数量 × 最大总重量+1」，标记处理每个物品时，在对应重量状态下是否选中了当前物品
• 计算完所有状态的最小成本后，先定位到满足重量要求的最低成本对应的最优总重量值，再从最后一个物品开始反向回溯，收集所有被标记为选中的物品索引

调整后的完整代码 #

import java.util.ArrayList;
import java.util.List;

public class KnapsackRecord {
    public static void main(String[] args) {
        final int[] weights = {20,40,10,30}, costs = {5,20,2,6};
        final int minWeight = 50;
        firstSolution(weights,costs,minWeight);
    }

    public static void firstSolution(int[] weights, int[] costs, int minWeight){
        int maxWeight = 0;
        for(final int weight: weights){
            maxWeight += weight;
        }
        int[] minCost = new int[maxWeight + 1];
        for(int i = 1; i <= maxWeight; i++){
            minCost[i] = Integer.MAX_VALUE;
        }
        // 新增：记录每个状态下的选中标记
        boolean[][] isChosen = new boolean[weights.length][maxWeight + 1];

        for(int i = 0; i < weights.length; i++){
            for(int j = maxWeight; j >= weights[i]; j--){
                if(minCost[j - weights[i]] != Integer.MAX_VALUE){
                    int newCost = minCost[j - weights[i]] + costs[i];
                    // 当新路径成本更优时，更新成本并标记选中当前物品
                    if(newCost < minCost[j]) {
                        minCost[j] = newCost;
                        isChosen[i][j] = true;
                    }
                }
            }
        }

        int answer = Integer.MAX_VALUE;
        int optimalWeight = 0;
        // 定位满足重量要求的最低成本对应的最优总重量
        for(int i = minWeight; i <= maxWeight; i++){
            if(minCost[i] < answer) {
                answer = minCost[i];
                optimalWeight = i;
            }
        }

        // 反向回溯收集选中的物品索引
        List<Integer> selectedIndex = new ArrayList<>();
        int currentWeight = optimalWeight;
        for(int i = weights.length - 1; i >= 0; i--) {
            if(isChosen[i][currentWeight]) {
                selectedIndex.add(i);
                currentWeight -= weights[i];
            }
            if(currentWeight == 0) break;
        }

        // 输出结果
        System.out.println("满足要求的最低成本：" + answer);
        System.out.println("最优解对应的物品索引集合：" + selectedIndex);
    }
}

运行结果说明 #

使用题目给出的示例输入运行后，输出为：

满足要求的最低成本：11
最优解对应的物品索引集合：[3, 0]

结果和题目描述的选中索引0（重量20、成本5）、索引3（重量30、成本6）的最优解完全匹配，反向回溯得到的索引顺序仅和遍历方向有关，不影响最终的物品集合正确性。

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