使用java语言解决0-1背包问题,要求随机生成若干个物品的数据(数据包括重量与价值),设置适当的背包承重,使用用动态规划法求解,记录运行时间与背包放入物品记录
时间: 2023-06-10 11:02:50 浏览: 116
0-1背包问题(Java版)
4星 · 用户满意度95%
好的,我理解了你的要求。以下是使用Java语言解决0-1背包问题的代码:
```java
import java.util.*;
public class KnapsackProblem {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 随机生成若干个物品的数据,包括重量和价值
System.out.print("请输入物品的数量:");
int n = scanner.nextInt();
int[] w = new int[n];
int[] v = new int[n];
Random random = new Random();
for (int i = 0; i < n; i++) {
w[i] = random.nextInt(10) + 1;
v[i] = random.nextInt(10) + 1;
System.out.println("物品" + (i+1) + "的重量为" + w[i] + ", 价值为" + v[i]);
}
// 设置背包的承重
System.out.print("请输入背包的承重:");
int c = scanner.nextInt();
// 使用动态规划法求解0-1背包问题
int[][] dp = new int[n+1][c+1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= c; j++) {
if (j < w[i-1]) {
dp[i][j] = dp[i-1][j];
} else {
dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1]);
}
}
}
// 记录运行时间和背包放入物品记录
int[] x = new int[n];
int j = c;
for (int i = n; i >= 1; i--) {
if (dp[i][j] > dp[i-1][j]) {
x[i-1] = 1;
j -= w[i-1];
}
}
System.out.println("背包的最大价值为" + dp[n][c] + ",放入物品的记录为:");
for (int i = 0; i < n; i++) {
if (x[i] == 1) {
System.out.println("物品" + (i+1));
}
}
System.out.println("运行时间:" + System.currentTimeMillis() + "毫秒");
}
}
```
以上代码使用了动态规划法求解0-1背包问题,同时记录了运行时间和背包放入物品的记录。希望能够解决你的问题。
阅读全文