0-1背包问题是很经典的算法问题:给定n种物品和一背包。物品i的重量是wi,价值是vi,背包最大容量是C。应该如何选择装入背包的物品,使得装入背包中物品的总价值最大?使用Java回溯法写出完整代码,在操作框输入物品数,背包成重量,每个物品重量和每个物品价值。然后输出最大价值和包中装了哪几件物品?
时间: 2023-10-02 15:12:15 浏览: 176
好的,我知道了。以下是Java回溯法解决0-1背包问题的代码实现:
```
import java.util.*;
public class Knapsack {
private static int n; // 物品数
private static int c; // 背包容量
private static int[] w; // 物品重量
private static int[] v; // 物品价值
private static int maxValue; // 最大价值
private static int[] solution; // 存储最优解
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print("请输入物品数:");
n = scanner.nextInt();
System.out.print("请输入背包容量:");
c = scanner.nextInt();
w = new int[n];
v = new int[n];
solution = new int[n];
System.out.println("请输入每个物品的重量和价值:");
for (int i = 0; i < n; i++) {
w[i] = scanner.nextInt();
v[i] = scanner.nextInt();
}
backTrack(0, 0, 0, new int[n]);
System.out.println("最大价值为:" + maxValue);
System.out.print("包中装了哪几件物品:");
for (int i = 0; i < n; i++) {
if (solution[i] == 1) {
System.out.print(i + 1 + " ");
}
}
}
private static void backTrack(int i, int cw, int cv, int[] x) {
if (i == n) { // 达到叶子节点
if (cv > maxValue) {
maxValue = cv; // 更新最大价值
solution = x.clone(); // 更新最优解
}
return;
}
if (cw + w[i] <= c) { // 装入第i个物品
x[i] = 1;
backTrack(i + 1, cw + w[i], cv + v[i], x);
x[i] = 0;
}
backTrack(i + 1, cw, cv, x); // 不装入第i个物品
}
}
```
你可以将以上代码复制到你的编辑器中进行运行,并按照提示输入数据。程序将输出最大价值和包中装了哪几件物品。
阅读全文