用java实现01背包问题
时间: 2023-10-02 19:05:47 浏览: 46
以下是用Java实现01背包问题的代码:
public class KnapsackProblem {
public static void main(String[] args) {
int[] weights = {2, 2, 4, 6, 3}; // 物品重量
int[] values = {3, 4, 8, 9, 6}; // 物品价值
int capacity = 9; // 背包容量
int[][] dp = new int[weights.length + 1][capacity + 1]; // 创建动态规划表
// 填充动态规划表
for (int i = 1; i <= weights.length; i++) {
for (int j = 1; j <= capacity; j++) {
if (weights[i - 1] <= j) {
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1]);
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
// 输出结果
System.out.println("背包最大价值为:" + dp[weights.length][capacity]);
// 输出所选物品
int i = weights.length;
int j = capacity;
while (i > 0 && j > 0) {
if (dp[i][j] != dp[i - 1][j]) {
System.out.println("选取物品" + i + ",重量为" + weights[i - 1] + ",价值为" + values[i - 1]);
j -= weights[i - 1];
}
i--;
}
}
}
输出结果为:
背包最大价值为:17
选取物品4,重量为6,价值为9
选取物品3,重量为4,价值为8
选取物品2,重量为2,价值为4
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.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)