java实现01背包问题
时间: 2024-06-22 19:02:10 浏览: 6
在Java中,0-1背包问题是一个经典的动态规划问题,用于解决物品分配问题,其中每种物品都有一定的价值和重量,目标是在不超过背包容量的情况下,选择组合以获得最大价值。以下是使用动态规划方法的一个基本实现:
```java
public class Knapsack {
private static int[] dp; // 动态规划数组,dp[i][j] 表示前i件物品在总重量不超过j时的最大价值
public static int knapSack(int W, int[] wt, int[] val, int n) {
dp = new int[n + 1][W + 1]; // 初始化二维数组,n为物品数量,W为背包容量
// 填充动态规划表
for (int i = 0; i <= n; i++) { // 遍历所有物品
for (int w = 0; w <= W; w++) { // 遍历所有可能的背包容量
if (i == 0 || w == 0) { // 如果没有物品或背包为空,价值为0
dp[i][w] = 0;
} else if (wt[i - 1] <= w) { // 当前物品重量小于等于背包剩余容量
dp[i][w] = Math.max(val[i - 1] + dp[i - 1][w - wt[i - 1]], dp[i - 1][w]); // 如果包含当前物品,取其价值加上不包含的价值(容量减少后的最大价值)
} else { // 当前物品重量大于背包剩余容量,直接用不包含当前物品的最大价值
dp[i][w] = dp[i - 1][w];
}
}
}
return dp[n][W]; // 返回背包在给定容量下的最大价值
}
// 示例:
public static void main(String[] args) {
int W = 50; // 背包容量
int[] wt = {10, 20, 30}; // 物品重量
int[] val = {60, 100, 120}; // 物品价值
int n = wt.length; // 物品数量
System.out.println(knapSack(W, wt, val, 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)