java 01背包问题
时间: 2023-10-14 13:20:16 浏览: 63
Java的01背包问题可以通过动态规划来解决。
首先,定义一个二维数组`dp`,其中`dp[i][j]`表示前`i`个物品在容量为`j`的背包中所能获得的最大价值。
然后,我们可以使用以下的递推公式来计算`dp`数组的值:
```
if (j < w[i])
dp[i][j] = dp[i-1][j];
else
dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]);
```
其中,`w[i]`和`v[i]`分别表示第`i`个物品的重量和价值。
最终的答案就是`dp[n][W]`,其中`n`表示物品的个数,`W`表示背包的容量。
下面是Java代码实现:
```java
public class KnapsackProblem {
public static int knapsack(int W, int[] w, int[] v) {
int n = w.length;
int[][] dp = new int[n+1][W+1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= W; j++) {
if (j < w[i-1])
dp[i][j] = dp[i-1][j];
else
dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1]);
}
}
return dp[n][W];
}
public static void main(String[] args) {
int W = 10;
int[] w = {2, 3, 4, 5};
int[] v = {3, 4, 5, 6};
int maxVal = knapsack(W, w, v);
System.out.println("The max value is: " + maxVal);
}
}
```
在上面的例子中,我们有4个物品,背包容量为10。物品的重量分别为2、3、4、5,价值分别为3、4、5、6。程序会输出最大价值为10。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_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)