背包算法，用java写一个

背包算法是一种求解最优化问题的算法，常用于动态规划问题中。下面是一个Java实现：

public class Knapsack {

    static int knapsack(int W, int wt[], int val[], int n) {
        int i, w;
        int K[][] = new int[n + 1][W + 1];

        for (i = 0; i <= n; i++) {
            for (w = 0; w <= W; w++) {
                if (i == 0 || w == 0)
                    K[i][w] = 0;
                else if (wt[i - 1] <= w)
                    K[i][w] = Math.max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w]);
                else
                    K[i][w] = K[i - 1][w];
            }
        }

        return K[n][W];
    }

    public static void main(String args[]) {
        int val[] = new int[] { 60, 100, 120 };
        int wt[] = new int[] { 10, 20, 30 };
        int W = 50;
        int n = val.length;
        System.out.println(knapsack(W, wt, val, n));
    }
}

在这个实现中，我们首先定义了一个静态方法`knapsack`，它接受四个参数：背包容量`W`、物品重量数组`wt`、物品价值数组`val`和物品数量`n`。它返回一个整数，表示能装进背包的最大价值。

算法的核心是一个二维数组`K`，它保存了在背包容量为`w`、前`i`个物品中选择的最大价值。我们使用两个嵌套的循环来填充这个数组。对于每个`i`和`w`的组合，我们需要考虑两种情况：

- 物品`i`的重量大于背包容量`w`，我们不能选择它，因此最大价值等于前`i-1`个物品中选择的最大价值。
- 物品`i`的重量小于等于背包容量`w`，我们可以选择它或不选择它。如果选择它，最大价值等于`val[i-1]`加上前`i-1`个物品在背包容量为`w-wt[i-1]`时选择的最大价值；如果不选择它，最大价值等于前`i-1`个物品在背包容量为`w`时选择的最大价值。我们在这两种情况中选择较大的值。

最后，我们在`main`方法中定义了一个简单的测试用例，将物品重量、价值和背包容量硬编码，然后输出结果。在这个测试用例中，最大价值为220，对应于选择前两个物品。