动态规划算法0/1背包问题java
时间: 2024-06-04 18:03:01 浏览: 24
以下是Java代码实现0/1背包问题的动态规划算法:
```java
public class Knapsack {
public static void main(String[] args) {
int[] weight = {2, 2, 6, 5, 4}; // 物品的重量
int[] value = {6, 3, 5, 4, 6}; // 物品的价值
int capacity = 10; // 背包的容量
int n = value.length;
int[][] dp = new int[n + 1][capacity + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= capacity; j++) {
if (weight[i - 1] > j) {
dp[i][j] = dp[i - 1][j];
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i - 1]] + value[i - 1]);
}
}
}
int res = dp[n][capacity];
System.out.println("背包能装的最大价值为:" + res);
int w = capacity;
for (int i = n; i > 0 && res > 0; i--) {
if (res != dp[i - 1][w]) {
System.out.println("物品" + i + "放入背包");
res -= value[i - 1];
w -= weight[i - 1];
}
}
}
}
```
相关推荐
![java](https://img-home.csdnimg.cn/images/20210720083646.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)