优先队列式分支界限法解决装载问题的java代码
时间: 2023-07-09 15:36:07 浏览: 48
以下是使用优先队列式分支界限法解决装载问题的Java代码:
```
import java.util.*;
public class BranchAndBound {
// 定义物品类
static class Item {
int weight;
int level;
int profit;
double bound;
public Item(int weight, int level, int profit, double bound) {
this.weight = weight;
this.level = level;
this.profit = profit;
this.bound = bound;
}
}
// 计算当前节点的上界
public static double calcUpperBound(int capacity, int level, int profit, int[] weights, int[] profits) {
double bound = profit;
int w = capacity;
for (int i = level; i < weights.length; i++) {
if (w >= weights[i]) {
bound += profits[i];
w -= weights[i];
} else {
bound += (double) profits[i] * w / weights[i];
break;
}
}
return bound;
}
// 优先队列式分支界限法
public static int knapsack(int capacity, int[] weights, int[] profits) {
PriorityQueue<Item> pq = new PriorityQueue<>(new Comparator<Item>() {
@Override
public int compare(Item o1, Item o2) {
return Double.compare(o2.bound, o1.bound);
}
});
double maxProfit = 0;
Item root = new Item(0, 0, 0, calcUpperBound(capacity, 0, 0, weights, profits));
pq.offer(root);
while (!pq.isEmpty()) {
Item node = pq.poll();
if (node.bound < maxProfit) {
continue;
}
if (node.level == weights.length) {
maxProfit = node.profit;
continue;
}
// 不选当前物品
Item left = new Item(node.weight, node.level + 1, node.profit, calcUpperBound(capacity - node.weight, node.level + 1, node.profit, weights, profits));
if (left.bound > maxProfit) {
pq.offer(left);
}
// 选当前物品
if (node.weight + weights[node.level] <= capacity) {
Item right = new Item(node.weight + weights[node.level], node.level + 1, node.profit + profits[node.level], calcUpperBound(capacity - node.weight - weights[node.level], node.level + 1, node.profit + profits[node.level], weights, profits));
if (right.bound > maxProfit) {
pq.offer(right);
}
}
}
return (int) maxProfit;
}
public static void main(String[] args) {
int capacity = 50;
int[] weights = {10, 20, 30};
int[] profits = {60, 100, 120};
int maxProfit = knapsack(capacity, weights, profits);
System.out.println("最大价值为:" + maxProfit);
}
}
```
相关推荐
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.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)