编辑代码

public class Knapsack {  
    private static final int MAX_VALUE = 100; // 背包容量  
    private static final int MAX_WEIGHT = 50; // 物品重量限制  
    private static final int ITEM_COUNT = 3; // 物品数量  
  
    public static void main(String[] args) {  
        int[][] items = {  
                {3, 4, 5}, // 物品1的重量、价值、数量  
                {2, 3, 2}, // 物品2的重量、价值、数量  
                {4, 5, 1}  // 物品3的重量、价值、数量  
        };  
        int capacity = 10; // 背包容量  
        System.out.println("背包容量：" + capacity);  
        System.out.println("物品信息：");  
        printItems(items);  
        System.out.println("最优解：" + branchAndBound(items, capacity));  
    }  
  
    private static int branchAndBound(int[][] items, int capacity) {  
        int maxValue = 0; // 最优解的价值  
        int bound = calculateBound(items); // 分支界限值  
        if (bound <= capacity) {  
            maxValue = calculateValue(items, capacity); // 最优解的价值，计算过程中更新最大价值  
        }  
        return maxValue;  
    }  
  
    private static int calculateBound(int[][] items) {  
        int totalWeight = 0; // 总重量  
        int totalValue = 0; // 总价值  
        for (int[] item : items) {  
            totalWeight += item[0]; // 计算总重量  
            totalValue += item[1]; // 计算总价值  
        }  
        int maxWeight = getMaxWeight(items); // 单个物品的最大重量  
        int bound = totalValue - (totalWeight - maxWeight) * (maxWeight - totalWeight + 1) / (totalWeight - maxWeight); // 分支界限公式  
        return bound;  
    }  
  
    private static int getMaxWeight(int[][] items) {  
        int maxWeight = Integer.MIN_VALUE; // 单个物品的最大重量初始化为负无穷大  
        for (int[] item : items) {  
            maxWeight = Math.max(maxWeight, item[0]); // 更新最大重量  
        }  
        return maxWeight;  
    }  
  
    private static int calculateValue(int[][] items, int capacity) {  
        int maxValue = Integer.MIN_VALUE; // 最优解的价值初始化为负无穷大  
        for (int i = 0; i <= ITEM_COUNT; i++) { // 分支：枚举选择物品的数量  
            for (int j = 0; j < items.length; j++) { // 分支：枚举选择每个物品  
                if (i == 0 || j == ITEM_COUNT) { // 剪枝：边界情况或已选择完所有物品，跳出循环  
                    continue;  
                }  
                if (items[j][0] <= capacity) { // 剪枝：当前物品的重量不超过背包容量，继续递归搜索  
                    capacity -= items[j][0]; // 减去当前物品的重量  
                    int value = calculateValue(items, capacity); // 递归搜索下一个物品，更新最大价值  
                    capacity += items[j][0]; // 恢复背包容量，回溯到上一层状态  
                    maxValue = Math.max(maxValue, value); // 更新最大价值  
                } else { // 剪枝：当前物品的重量超过背包容量，跳出循环，回溯到上一层状态  
                    capacity += items[j][0]; // 恢复背包容量，回溯到上一层状态  
                }  
            }  
        }  
        return maxValue; // 最优解的价值就是所有分支中最大的价值  
    }  
  
    private static void printItems(int[][] items) {  
        for (int[] item : items) {  
            System.out.println("物品：" + item[2] + "，重量：" + item[0] + "，价值：" + item[1]);  
        }  
    }  
}