void search (int t,int[] x) { if (t>n){ output(x); return; } for (int i=0;i<=1;i++) { x[t]=i; if (legal(t, i, x)) search (t+1,x); } } (1)上面的程序采用的是哪一种策略?空间搜索树是什么类型?解向量x的初值是什么? (2)用这段程序是否可以求解0-1背包问题?如果能,请写出合法性判定函数 legal(t, i, x)。如果不能,请说明理由。
时间: 2023-12-05 08:05:55 浏览: 52
(1) 上面的程序采用的是回溯算法(backtracking algorithm)策略,空间搜索树是二叉树。解向量x的初值是一个长度为n+1的数组,初始值为0。
(2) 这段程序可以用于求解0-1背包问题。合法性判定函数legal(t, i, x)应该判断前t个物品放入背包中的情况下,是否满足背包容量限制以及当前价值是否大于已有的最优解。其中,t表示当前考虑的物品编号,i表示当前物品选择放入背包还是不放入背包,x为长度为n+1的数组,表示前t-1个物品放入背包的情况,x[t]表示第t个物品是否放入背包。判断背包容量是否超限可以用如下代码实现:
```
boolean legal(int t, int i, int[] x) {
int weight = 0;
for (int j = 1; j < t; j++) {
weight += x[j] * w[j];
}
weight += i * w[t];
return weight <= c;
}
```
其中,w[j]表示第j个物品的重量,c表示背包的容量限制。判断当前价值是否大于已有的最优解可以用如下代码实现:
```
boolean legal(int t, int i, int[] x) {
int weight = 0, value = 0;
for (int j = 1; j < t; j++) {
weight += x[j] * w[j];
value += x[j] * v[j];
}
weight += i * w[t];
value += i * v[t];
return weight <= c && value > bestValue;
}
```
其中,v[j]表示第j个物品的价值,bestValue表示当前已有的最优解的价值。如果以上两个条件都满足,则返回true;否则返回false。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)