java:动态规划法实现背包问题
时间: 2023-12-10 12:34:55 浏览: 41
以下是Java中使用动态规划法实现0-1背包问题的代码和解释:
```java
public class KnapsackProblem {
public static void main(String[] args) {
int[] weights = {2, 2, 6, 5, 4}; // 物品重量
int[] values = {6, 3, 5, 4, 6}; // 物品价值
int capacity = 10; // 背包容量
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 (weights[i - 1] > j) { // 当前物品重量大于背包容量,无法放入
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]);
}
}
}
System.out.println("背包能装的最大价值为:" + dp[n][capacity]); // 输出最大价值
}
}
```
解释:
1. 首先定义物品重量数组`weights`、物品价值数组`values`和背包容量`capacity`,以及物品数量`n`。
2. 创建一个二维数组`dp`,其中`dp[i][j]`表示前`i`个物品放入容量为`j`的背包中所能获得的最大价值。
3. 初始化第一行和第一列为0,表示背包容量为0或没有物品时,最大价值均为0。
4. 从第二行开始,依次考虑每个物品是否放入背包中。如果当前物品重量大于背包容量,无法放入,最大价值与前`i-1`个物品相同;否则,比较放入和不放入的价值大小,取较大值作为当前状态的最大价值。
5. 最终输出`dp[n][capacity]`,即前`n`个物品放入容量为`capacity`的背包中所能获得的最大价值。