编辑代码

public class BitVectorKnapsack {
    public static void main(String[] args) {
        int[] weights = {2, 2, 3, 5};
        int[] values = {2, 3, 4, 7};
        int capacity = 5;

        int maxValue = knapsack(weights, values, capacity);
        System.out.println("Maximum value: " + maxValue);
    }

    public static int knapsack(int[] weights, int[] values, int capacity) {
        int n = weights.length;
        int maxCombinations = 1 << n; // 2^n
        int[] dp = new int[maxCombinations];

        for (int mask = 0; mask < maxCombinations; mask++) {
            int currentWeight = 0;
            int totalValue = 0;

            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) {
                    currentWeight += weights[i];
                    totalValue += values[i];
                }
            }

            if (currentWeight <= capacity) {
                dp[mask] = Math.max(dp[mask], totalValue);
            } else {
                dp[mask] = 0;
            }
        }

        return dp[maxCombinations - 1];
    }
}