解决0-1背包问题,要求使用java语言随机生成若干个物品的数据(重量与价值),设置适当的背包承重,用递归法求解,记录运行时间,记录物品选择;
时间: 2024-05-12 09:16:49 浏览: 6
好的,我了解您的要求,以下是Java语言实现0-1背包问题的代码,以及记录运行时间和物品选择的代码:
```
import java.util.Arrays;
import java.util.Random;
public class KnapsackProblem {
public static void main(String[] args) {
int n = 10; //物品个数
int[] weights = new int[n]; //重量数组
int[] values = new int[n]; //价值数组
int maxWeight = 50; //背包最大承重
//随机生成物品的重量和价值
Random rand = new Random();
for (int i = 0; i < n; i++) {
weights[i] = rand.nextInt(maxWeight) + 1;
values[i] = rand.nextInt(100) + 1;
}
long startTime = System.currentTimeMillis(); //记录开始时间
boolean[] selected = new boolean[n]; //记录物品的选择情况
int maxValue = knapsack(0, weights, values, maxWeight, selected); //求解0-1背包问题
long endTime = System.currentTimeMillis(); //记录结束时间
//输出结果
System.out.println("物品重量:" + Arrays.toString(weights));
System.out.println("物品价值:" + Arrays.toString(values));
System.out.println("背包最大承重:" + maxWeight);
System.out.println("最大价值:" + maxValue);
System.out.print("选择的物品:");
for (int i = 0; i < n; i++) {
if (selected[i]) {
System.out.print((i + 1) + " ");
}
}
System.out.println();
System.out.println("运行时间:" + (endTime - startTime) + "ms");
}
/**
* 递归求解0-1背包问题
*
* @param i 当前考虑的物品
* @param weights 物品重量数组
* @param values 物品价值数组
* @param maxWeight 背包最大承重
* @param selected 物品选择情况数组
* @return 最大价值
*/
public static int knapsack(int i, int[] weights, int[] values, int maxWeight, boolean[] selected) {
if (i == weights.length) {
return 0;
} else if (weights[i] > maxWeight) {
return knapsack(i + 1, weights, values, maxWeight, selected);
} else {
boolean[] selected1 = Arrays.copyOf(selected, selected.length);
selected1[i] = true;
int maxValue1 = knapsack(i + 1, weights, values, maxWeight - weights[i], selected1) + values[i];
int maxValue2 = knapsack(i + 1, weights, values, maxWeight, selected);
if (maxValue1 > maxValue2) {
for (int j = 0; j < selected.length; j++) {
selected[j] = selected1[j];
}
return maxValue1;
} else {
return maxValue2;
}
}
}
}
```
该程序会随机生成10个物品的重量和价值,背包最大承重为50。运行结束后,会输出最大价值、选择的物品、运行时间等信息。注意选择的物品是从1开始编号的。
希望对您有所帮助!
相关推荐
![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)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)