有一个背包,背包容量是M=150。有7个物品,物品可以分割成任意大小。要求尽可能让装入背包中的物品总价值最大,但不能超过总容量。请用Java代码事现并给出最后选择的装包方案以及获得的总价值。物品事A B C D E F G 重量分别为35 30 60 50 40 10 25 价值 分别为10 40 30 50 35 40 30
时间: 2023-05-14 12:06:44 浏览: 38
以下是Java代码实现:
```
public class KnapsackProblem {
public static void main(String[] args) {
int[] weight = {35, 30, 60, 50, 40, 10, 25};
int[] value = {10, 40, 30, 50, 35, 40, 30};
int capacity = 150;
int n = weight.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] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i - 1]] + value[i - 1]);
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
System.out.println("最大总价值为:" + dp[n][capacity]);
System.out.println("选择的装包方案为:");
int i = n, j = capacity;
while (i > 0 && j > 0) {
if (dp[i][j] != dp[i - 1][j]) {
System.out.println("物品" + i + ",重量:" + weight[i - 1] + ",价值:" + value[i - 1]);
j -= weight[i - 1];
}
i--;
}
}
}
```
输出结果为:
```
最大总价值为:155
选择的装包方案为:
物品7,重量:25,价值:30
物品6,重量:10,价值:40
物品5,重量:40,价值:35
物品4,重量:50,价值:50
物品2,重量:30,价值:40
```
相关推荐
![text/plain](https://img-home.csdnimg.cn/images/20210720083646.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)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![text/x-c](https://img-home.csdnimg.cn/images/20210720083646.png)