嘿，我来帮你把这个0-1背包的实现完善好，让它不光能算出最大价值，还能返回对应的最优物品集合！

首先，你原来的代码已经搭好了DP矩阵的架子，我先补全填充逻辑，再加上回溯找选中物品的关键部分——这是拿到具体物品集合的核心步骤。

完整实现代码 #

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

public class KnapsackSolver {
    // 返回最优解对应的物品索引列表（原数组从0开始计数）
    public static List<Integer> knapsackWithItems(int val[], int wt[], int W) {
        int itemCount = wt.length;
        // DP矩阵：V[i][w] 表示前i个物品、背包容量为w时的最大价值
        int[][] valueMatrix = new int[itemCount + 1][W + 1];

        // 初始化边界：0个物品或0容量时，价值都是0
        for (int col = 0; col <= W; col++) {
            valueMatrix[0][col] = 0;
        }
        for (int row = 0; row <= itemCount; row++) {
            valueMatrix[row][0] = 0;
        }

        // 填充DP矩阵
        for (int i = 1; i <= itemCount; i++) {
            for (int currentCapacity = 1; currentCapacity <= W; currentCapacity++) {
                int currentItemWeight = wt[i - 1];
                int currentItemValue = val[i - 1];

                if (currentItemWeight > currentCapacity) {
                    // 当前物品太重，放不进去，直接继承上一行的结果
                    valueMatrix[i][currentCapacity] = valueMatrix[i - 1][currentCapacity];
                } else {
                    // 选「不放当前物品」或「放当前物品」里价值更高的那个
                    valueMatrix[i][currentCapacity] = Math.max(
                        valueMatrix[i - 1][currentCapacity],
                        valueMatrix[i - 1][currentCapacity - currentItemWeight] + currentItemValue
                    );
                }
            }
        }

        // 回溯找出选中的物品
        List<Integer> selectedItems = new ArrayList<>();
        int currentItemIdx = itemCount;
        int remainingCapacity = W;

        while (currentItemIdx > 0 && remainingCapacity > 0) {
            // 如果当前行的价值和上一行不一样，说明选中了这个物品
            if (valueMatrix[currentItemIdx][remainingCapacity] != valueMatrix[currentItemIdx - 1][remainingCapacity]) {
                // 转换为原数组的0索引
                selectedItems.add(currentItemIdx - 1);
                // 减去当前物品的重量，继续找剩下的物品
                remainingCapacity -= wt[currentItemIdx - 1];
            }
            currentItemIdx--;
        }

        // 可选：如果需要按原物品顺序输出，解开下面的注释
        // Collections.reverse(selectedItems);

        return selectedItems;
    }

    // 测试用例，方便你验证
    public static void main(String[] args) {
        int[] itemValues = {60, 100, 120};
        int[] itemWeights = {10, 20, 30};
        int knapsackCapacity = 50;

        List<Integer> selected = knapsackWithItems(itemValues, itemWeights, knapsackCapacity);
        System.out.println("选中的物品索引（0开始）：" + selected);
        System.out.println("总价值：" + calculateTotalValue(itemValues, selected));
    }

    // 辅助方法：计算选中物品的总价值
    private static int calculateTotalValue(int[] val, List<Integer> selectedItems) {
        int total = 0;
        for (int idx : selectedItems) {
            total += val[idx];
        }
        return total;
    }
}

关键部分解释 #

1. DP矩阵填充：
   对于每个物品和每个可能的背包容量，我们判断：

   • 如果物品太重放不下，直接沿用「不放这个物品」的最大价值（上一行同列的值）；
   • 如果放得下，就对比「不放这个物品」和「放这个物品（加上剩余容量的最优价值）」，取大的那个。

2. 回溯找物品：
   从矩阵的右下角（最后一个物品、满容量）开始倒推：

   • 如果当前行的价值和上一行不同，说明这个物品被选中了（因为放入它才让价值提升）；
   • 然后减去该物品的重量，继续往前找剩下的物品；
   • 最后收集到的索引是从后往前的，要是需要按原物品顺序输出，解开Collections.reverse(selectedItems)的注释就行。

测试结果 #

运行测试用例的话，输出会是：

选中的物品索引（0开始）：[2, 1]
总价值：220

对应重量30+20=50，价值120+100=220，确实是这个用例的最优解。

内容的提问来源于stack exchange，提问作者S. N