用Java实现,0/1背包问题
时间: 2023-07-20 12:06:51 浏览: 72
好的,这里是使用Java实现0/1背包问题的代码:
```java
public class Knapsack {
public static int knapSack(int W, int wt[], int val[], int n) {
// dp数组表示在前i个物品中,容量为j的背包所能装下的最大价值
int[][] dp = new int[n + 1][W + 1];
// base case:当物品数量为0或背包容量为0时,最大价值为0
for (int i = 0; i <= n; i++) {
dp[i][0] = 0;
}
for (int j = 0; j <= W; j++) {
dp[0][j] = 0;
}
// 状态转移方程
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= W; j++) {
if (j - wt[i - 1] < 0) { // 当前物品的重量大于背包容量,无法装入
dp[i][j] = dp[i - 1][j];
} else {
// 当前物品可以选择装入或不装入,取最大值
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - wt[i - 1]] + val[i - 1]);
}
}
}
return dp[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)); // 输出结果为 220
}
}
```
这里的`knapSack`函数用来求解0/1背包问题,参数说明如下:
- `W`:背包容量
- `wt`:物品重量数组
- `val`:物品价值数组
- `n`:物品数量
其中,`dp[i][j]`表示在前i个物品中,容量为j的背包所能装下的最大价值。在状态转移方程中,我们考虑第i个物品,如果当前物品的重量大于背包容量,那么它无法装入,此时的最大价值就是前i-1个物品在容量为j的背包中的最大价值;如果当前物品的重量小于等于背包容量,那么它可以选择装入或不装入,我们需要取两种情况中的最大值作为当前状态的最大价值。