编辑代码

public class KnapsackProblem {
    
    public static int knapsack(int capacity, int[] weights, int[] values) {
        int n = weights.length;
        int max = 0;
        
        // 生成所有可能的组合
        int combinations = (int) Math.pow(2, n);
        for (int i = 0; i < combinations; i++) {
            int currentWeight = 0;
            int currentValue = 0;
            
            // 检查二进制中的每一位是否为1
            for (int j = 0; j < n; j++) {
                if ((i & (1 << j)) != 0) {
                    currentWeight += weights[j];
                    currentValue += values[j];
                }
            }
            
            // 判断当前组合是否满足条件且总价值最大
            if (currentWeight <= capacity && currentValue > max) {
                max = currentValue;
            }
        }
        
        return max;
    }
    
    public static void main(String[] args) {
        int capacity = 10;
        int[] weights = {2, 3, 4, 5};
        int[] values = {3, 4, 5, 6};
        System.out.println(knapsack(capacity, weights, values)); // 输出 10
    }
}