用java写一个1背包算法
时间: 2024-05-09 12:15:43 浏览: 20
以下是Java实现的01背包算法:
```java
public class Knapsack01 {
public static int knapsack01(int[] weights, int[] values, int capacity) {
int n = weights.length;
int[][] dp = new int[n + 1][capacity + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= capacity; j++) {
if (j < weights[i - 1]) {
dp[i][j] = dp[i - 1][j];
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1]);
}
}
}
return dp[n][capacity];
}
}
```
其中,weights和values分别表示物品的重量和价值,capacity表示背包的容量。dp[i][j]表示前i个物品放入容量为j的背包中所能获得的最大价值。
具体实现中,我们先初始化dp数组,然后使用双重循环遍历所有可能的物品和容量组合,根据当前物品重量是否超过当前容量来判断是否选择该物品,最后返回dp[n][capacity]即可。