0-1背包问题是很经典的算法问题:给定n种物品和一背包。物品i的重量是wi,价值是vi,背包最大容量是C。应该如何选择装入背包的物品,使得装入背包中物品的总价值最大?使用Java回溯法写出完整代码,在操作框分别输入输入物品数,背包承重量,分别输入每个物品重量和每个物品价值。然后输出最大价值和包中装了哪几件物品?
时间: 2023-12-02 10:22:14 浏览: 30
好的,以下是Java回溯法解决0-1背包问题的代码实现:
```
import java.util.Scanner;
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 (cw > c) { // 超过背包容量
return;
}
if (i == n) { // 达到叶子节点
if (cv > maxValue) {
maxValue = cv; // 更新最大价值
solution = x.clone(); // 更新最优解
}
return;
}
x[i] = 1; // 装入第i个物品
backTrack(i + 1, cw + w[i], cv + v[i], x);
x[i] = 0; // 不装入第i个物品
backTrack(i + 1, cw, cv, x);
}
}
```
你可以将以上代码复制到你的编辑器中进行运行,并按照提示输入数据。程序将输出最大价值和包中装了哪几件物品。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.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)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)