01背包 java实现
时间: 2023-10-16 18:11:05 浏览: 48
以下是一个简单的01背包问题的Java实现:
```
public class Knapsack {
/**
* 01背包问题
* @param W 背包容量
* @param wt 物品重量
* @param val 物品价值
* @param n 物品个数
* @return 最大价值
*/
public static int knapsack(int W, int[] wt, int[] val, int n) {
int[][] dp = new int[n + 1][W + 1];
// 初始化第一行和第一列为0
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= W; j++) {
if (i == 0 || j == 0) {
dp[i][j] = 0;
} else if (wt[i - 1] <= j) {
// 当前物品可以装入背包
dp[i][j] = Math.max(val[i - 1] + dp[i - 1][j - wt[i - 1]], dp[i - 1][j]);
} else {
// 当前物品无法装入背包
dp[i][j] = dp[i - 1][j];
}
}
}
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 = 3; // 物品个数
System.out.println("最大价值为:" + knapsack(W, wt, val, n));
}
}
```
输出结果:
```
最大价值为:220
```
这个例子中,背包容量为50,有3个物品,其重量分别为10、20、30,价值分别为60、100、120。最终输出的结果为220,表示在背包容量为50的情况下,能够装入的最大价值为220。
相关推荐
![](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)