编辑代码

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

public class Knapsack {

    static class Item {
        int weight;
        int value;

        public Item(int weight, int value) {
            this.weight = weight;
            this.value = value;
        }
    }

    public static void main(String[] args) {
        // 物品列表
        Item[] items = {
                new Item(10, 60),
                new Item(20, 100),
                new Item(30, 120)
        };
        // 背包容量
        int capacity = 50;

        // 使用回溯算法求解
        List<Item> bestSolution = knapsack(items, capacity);

        // 打印最佳方案
        System.out.println("最佳方案：");
        int totalWeight = 0;
        int totalValue = 0;
        for (Item item : bestSolution) {
            System.out.println("  物品重量：" + item.weight + ", 物品价值：" + item.value);
            totalWeight += item.weight;
            totalValue += item.value;
        }
        System.out.println("  总重量：" + totalWeight);
        System.out.println("  总价值：" + totalValue);
    }

    // 回溯算法求解装载问题
    private static List<Item> knapsack(Item[] items, int capacity) {
        // 初始化结果列表
        List<Item> bestSolution = new ArrayList<>();
        // 初始化最大价值
        int maxValue = 0;

        // 递归搜索所有方案
        knapsackHelper(items, capacity, 0, new ArrayList<>(), 0, bestSolution, maxValue);

        return bestSolution;
    }

    // 回溯算法递归函数
    private static void knapsackHelper(Item[] items, int capacity, int index, List<Item> currentSolution, int currentValue,
                                     List<Item> bestSolution, int maxValue) {
        // 递归结束条件：所有物品都已考虑
        if (index == items.length) {
            // 更新最佳方案
            if (currentValue > maxValue) {
                bestSolution.clear();
                bestSolution.addAll(currentSolution);
                maxValue = currentValue;
            }
            return;
        }

        // 考虑当前物品
        Item currentItem = items[index];

        // 不选当前物品
        knapsackHelper(items, capacity, index + 1, currentSolution, currentValue, bestSolution, maxValue);

        // 选当前物品
        if (capacity >= currentItem.weight) {
            // 更新当前方案
            currentSolution.add(currentItem);
            currentValue += currentItem.value;

            // 递归搜索下一层
            knapsackHelper(items, capacity - currentItem.weight, index + 1, currentSolution, currentValue, bestSolution, maxValue);

            // 回溯：移除当前物品
            currentSolution.remove(currentItem);
            currentValue -= currentItem.value;
        }
    }
}