使用Java语言,蛮力求解0/1背包问题
时间: 2024-01-16 15:03:10 浏览: 32
好的,以下是使用Java语言的暴力求解0/1背包问题的代码:
```java
public class Knapsack {
public static int knapsack(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];
}
public static void main(String[] args) {
int[] weights = {2, 3, 4, 5};
int[] values = {3, 4, 5, 6};
int capacity = 8;
System.out.println(knapsack(weights, values, capacity));
}
}
```
其中,`weights`数组是物品的重量,`values`数组是物品的价值,`capacity`是背包的容量。`dp[i][j]`表示前i个物品能够装入容量为j的背包中的最大价值。在计算`dp[i][j]`时,有两种情况:第一种是第i个物品不能装入背包中,此时`dp[i][j] = dp[i-1][j]`;第二种是第i个物品能够装入背包中,此时`dp[i][j] = dp[i-1][j-weights[i-1]] + values[i-1]`。最终的答案是`dp[n][capacity]`,其中n是物品的数量。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)