现有编号分别为{a,b,c,d,e}的五件物品,它们的重量和价值如下表1所示,背包的容量为10,使用动态规划算法求得装入背包物品的最大价值 表1 物品 a b c d e 重量 3 2 4 4 6 价值 5 4 4 7 5用java
时间: 2024-02-13 12:00:10 浏览: 25
好的,以下是Java代码实现:
```java
public class Knapsack {
public static void main(String[] args) {
int[] w = {3, 2, 4, 4, 6}; // 物品重量
int[] v = {5, 4, 4, 7, 5}; // 物品价值
int n = 5; // 物品数量
int c = 10; // 背包容量
int[][] dp = new int[n + 1][c + 1]; // dp数组,初始化为0
// 动态规划
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= c; j++) {
if (j >= w[i - 1]) { // 能够装下第i个物品
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + v[i - 1]);
} else { // 装不下第i个物品
dp[i][j] = dp[i - 1][j];
}
}
}
System.out.println("装入背包的最大价值为:" + dp[n][c]); // 输出结果
}
}
```
输出结果为:装入背包的最大价值为:16
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![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_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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)