背包问题是很经典的算法问题:给定n种物品和一背包。物品i的重量是wi,价值是vi,背包最大容量是C。假设物品可拆分,在装入物品时可以选择只装入物品的一部分,应该如何选择装入背包的物品,使得装入背包中物品的总价值最大。用键盘输入,java解决
时间: 2023-10-03 21:04:55 浏览: 71
以下是一个Java的实现,采用动态规划的方式求解背包问题:
```java
import java.util.Scanner;
public class KnapsackProblem {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 读取输入的物品数量和背包容量
int n = scanner.nextInt();
int C = scanner.nextInt();
// 读取每个物品的重量和价值
int[] w = new int[n];
int[] v = new int[n];
for (int i = 0; i < n; i++) {
w[i] = scanner.nextInt();
v[i] = scanner.nextInt();
}
// 创建一个二维数组来保存子问题的解
int[][] dp = new int[n + 1][C + 1];
// 填充数组
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= C; j++) {
if (w[i - 1] > j) {
// 当前物品的重量大于当前背包的容量,无法放入,继承前一个子问题的解
dp[i][j] = dp[i - 1][j];
} else {
// 当前物品可以放入背包,需要比较放和不放两种情况,选择价值更大的方案
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - w[i - 1]] + v[i - 1]);
}
}
}
// 输出最终结果
System.out.println(dp[n][C]);
}
}
```
以上代码中,我们首先读取输入的物品数量n和背包容量C,以及每个物品的重量w和价值v。接着,我们创建一个二维数组dp来保存子问题的解,其中dp[i][j]表示前i个物品放入容量为j的背包中的最大价值。
接下来,我们通过动态规划的方式来填充dp数组。对于每个子问题,我们有两种选择:不放当前物品,或者放当前物品。如果当前物品的重量大于当前背包容量,那么无法放入该物品,此时继承前一个子问题的解。如果当前物品可以放入背包,那么需要比较放和不放两种情况,选择价值更大的方案。最终,dp[n][C]就是我们要求的最大价值。
我们可以通过以下输入来测试程序:
```
4 5
1 2
2 4
3 4
4 5
```
这里有4个物品,背包容量为5,物品的重量和价值分别为:
- 物品1:重量1,价值2
- 物品2:重量2,价值4
- 物品3:重量3,价值4
- 物品4:重量4,价值5
程序输出的结果应该是10,表示最大价值为10。
阅读全文