编辑代码

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

public class ZeroOneKnapsack {

    private int[] weights;
    private int[] values;
    private int capacity;
    private List<Integer> bestSolution;
    private int bestValue;

    public ZeroOneKnapsack(int[] weights, int[] values, int capacity) {
        this.weights = weights;
        this.values = values;
        this.capacity = capacity;
        this.bestSolution = new ArrayList<>();
        this.bestValue = 0;
    }

    public void solve() {
        backtrack(0, 0, 0, new ArrayList<>());
    }

    private void backtrack(int index, int currentWeight, int currentValue, List<Integer> currentSolution) {
        // 递归边界：所有物品都遍历完
        if (index == weights.length) {
            // 更新最佳解
            if (currentValue > bestValue) {
                bestValue = currentValue;
                bestSolution = new ArrayList<>(currentSolution);
            }
            return;
        }

        // 不选择当前物品
        backtrack(index + 1, currentWeight, currentValue, currentSolution);

        // 选择当前物品
        if (currentWeight + weights[index] <= capacity) {
            currentSolution.add(index);
            backtrack(index + 1, currentWeight + weights[index], currentValue + values[index], currentSolution);
            currentSolution.remove(currentSolution.size() - 1); // 回溯
        }
    }

    public List<Integer> getBestSolution() {
        return bestSolution;
    }

    public int getBestValue() {
        return bestValue;
    }

    public static void main(String[] args) {
        int[] weights = {10, 20, 30};
        int[] values = {60, 100, 120};
        int capacity = 50;

        ZeroOneKnapsack knapsack = new ZeroOneKnapsack(weights, values, capacity);
        knapsack.solve();

        System.out.println("最佳解：");
        System.out.println("物品索引：" + knapsack.getBestSolution());
        System.out.println("最大价值：" + knapsack.getBestValue());
    }
}