用java实现背包算法

以下是使用Java实现背包算法的示例代码：

public class Knapsack {
    // 物品重量
    private int[] weights;
    // 物品价值
    private int[] values;
    // 背包容量
    private int capacity;

    public Knapsack(int[] weights, int[] values, int capacity) {
        this.weights = weights;
        this.values = values;
        this.capacity = capacity;
    }

    /**
     * 使用动态规划求解背包问题
     * @return 能够获取的最大价值
     */
    public int solve() {
        int n = weights.length;
        int[][] dp = new int[n + 1][capacity + 1];

        // 初始化第一行和第一列
        for (int i = 0; i <= n; i++) {
            dp[i][0] = 0;
        }
        for (int j = 0; j <= capacity; j++) {
            dp[0][j] = 0;
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= capacity; j++) {
                if (weights[i - 1] > j) {
                    // 当前物品放不下，不选
                    dp[i][j] = dp[i - 1][j];
                } else {
                    // 当前物品可以放入背包，选或不选
                    dp[i][j] = Math.max(dp[i - 1][j], values[i - 1] + dp[i - 1][j - weights[i - 1]]);
                }
            }
        }

        return dp[n][capacity];
    }

    public static void main(String[] args) {
        int[] weights = {2, 5, 4, 3};
        int[] values = {3, 7, 5, 2};
        int capacity = 10;
        Knapsack knapsack = new Knapsack(weights, values, capacity);
        System.out.println(knapsack.solve()); // Output: 12
    }
}

在这个示例中，我们使用动态规划来解决背包问题。我们创建一个二维数组 dp，其中 dp[i][j] 表示前 i 个物品，容量为 j 的背包所能获取的最大价值。然后，我们通过填充第一行和第一列的值来初始化数组。接下来，我们使用一个双重循环来填充剩余的单元格。在每个单元格中，我们检查当前物品是否可以放入背包中。如果当前物品放不下，那么我们不选它，并将值设置为 dp[i-1][j]。否则，我们可以选择将它放入背包中或不选它。我们将两种情况中的更大值存储在 dp[i][j] 中。最后，我们返回 dp[n][capacity]，即最后一个单元格的值，它表示在背包容量为 capacity 时所能获取的最大价值。