使用蛮力法和动态规划算法解决0/1背包问题的java代码

1. 蛮力法

蛮力法解决0/1背包问题的思路是枚举所有可能的物品选取方案，然后找出其中满足背包容量限制且总价值最大的方案。

代码如下：

public class BruteForceSolution {
    // 物品重量数组
    private int[] weights;
    // 物品价值数组
    private int[] values;
    // 背包容量
    private int capacity;
    // 物品数量
    private int n;
    // 最大总价值
    private int maxTotalValue;

    public BruteForceSolution(int[] weights, int[] values, int capacity) {
        this.weights = weights;
        this.values = values;
        this.capacity = capacity;
        this.n = weights.length;
        this.maxTotalValue = 0;
    }

    public int getMaxTotalValue() {
        return maxTotalValue;
    }

    public void solve() {
        int[] selected = new int[n]; // 记录选取的物品
        int[] indexes = new int[n]; // 记录当前物品的选取状态
        for (int i = 0; i < n; i++) {
            indexes[i] = 0;
        }

        while (true) {
            int totalWeight = 0;
            int totalValue = 0;

            // 统计当前方案的总重量和总价值
            for (int i = 0; i < n; i++) {
                if (indexes[i] == 1) {
                    totalWeight += weights[i];
                    totalValue += values[i];
                }
            }

            // 更新最大总价值
            if (totalValue > maxTotalValue && totalWeight <= capacity) {
                maxTotalValue = totalValue;
                System.arraycopy(indexes, 0, selected, 0, n);
            }

            // 枚举所有可能的物品选取状态
            int k = n - 1;
            while (k >= 0 && indexes[k] == 1) {
                indexes[k] = 0;
                k--;
            }
            if (k < 0) {
                break;
            }
            indexes[k] = 1;
        }

        // 输出最优方案
        System.out.print("Selected items: ");
        for (int i = 0; i < n; i++) {
            if (selected[i] == 1) {
                System.out.print(i + " ");
            }
        }
        System.out.println();
    }
}

2. 动态规划算法

动态规划算法解决0/1背包问题的思路是将问题分解为若干子问题，并通过子问题的最优解来推导出原问题的最优解。

代码如下：

public class DynamicProgrammingSolution {
    // 物品重量数组
    private int[] weights;
    // 物品价值数组
    private int[] values;
    // 背包容量
    private int capacity;
    // 物品数量
    private int n;
    // 最大总价值
    private int maxTotalValue;

    public DynamicProgrammingSolution(int[] weights, int[] values, int capacity) {
        this.weights = weights;
        this.values = values;
        this.capacity = capacity;
        this.n = weights.length;
        this.maxTotalValue = 0;
    }

    public int getMaxTotalValue() {
        return maxTotalValue;
    }

    public void solve() {
        int[][] dp = new int[n + 1][capacity + 1]; // dp数组，dp[i][j]表示前i个物品在容量为j时的最大总价值

        // 初始化dp数组，当容量为0时，最大总价值为0；当物品数量为0时，最大总价值也为0
        for (int i = 0; i <= n; i++) {
            dp[i][0] = 0;
        }
        for (int j = 0; j <= capacity; j++) {
            dp[0][j] = 0;
        }

        // 根据递推公式计算dp数组的值
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= capacity; j++) {
                if (weights[i - 1] <= j) {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1]);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }

        // 最大总价值即为dp[n][capacity]
        maxTotalValue = dp[n][capacity];

        // 输出最优方案
        int[] selected = new int[n]; // 记录选取的物品
        int j = capacity;
        for (int i = n; i >= 1; i--) {
            if (dp[i][j] > dp[i - 1][j]) {
                selected[i - 1] = 1;
                j -= weights[i - 1];
            }
        }
        System.out.print("Selected items: ");
        for (int i = 0; i < n; i++) {
            if (selected[i] == 1) {
                System.out.print(i + " ");
            }
        }
        System.out.println();
    }
}