小明上学,老师布置了 n 个作业,每个作业恰好需要一天做完,每个作业都有最后提交时间ti及其逾期的扣分ki。已知作业n = 3,每个作业的最后提交时间t = [1,3,1],作业逾期扣分k = [6,2,3]。以输入n = 0时作为结束,请给出小明做作业的顺序,以便扣最少的分数。使用分支界限法写出Java代码并分析
时间: 2024-02-18 11:06:14 浏览: 20
好的,这是一个典型的作业调度问题,可以使用贪心算法或分支界限法来解决。在这里,我会给出使用分支界限法解决该问题的Java代码,并对其进行简要分析。
首先,我们需要定义一个作业(Job)类来表示每个作业的信息,包括作业编号、最后提交时间和逾期扣分:
```java
public class Job {
int id;
int deadline;
int penalty;
public Job(int id, int deadline, int penalty) {
this.id = id;
this.deadline = deadline;
this.penalty = penalty;
}
}
```
接下来,我们可以使用一个优先队列(PriorityQueue)来保存待处理的节点。每次取出队列中的最优节点,如果该节点的界限小于当前的最优解,则将该节点的子节点加入队列中。具体来说,我们可以枚举每个作业,计算加入该作业后的总逾期扣分,并计算剩余作业的最大截止时间。如果总逾期扣分小于当前最优解,就将该节点加入队列中。每次加入节点时,我们需要计算该节点的界限,以便与当前最优解进行比较。
下面是使用分支界限法解决该问题的Java代码:
```java
import java.util.Comparator;
import java.util.PriorityQueue;
public class BranchAndBound {
public static int schedule(int[] deadlines, int[] penalties) {
int n = deadlines.length;
int maxDeadline = 0;
for (int i = 0; i < n; i++) {
maxDeadline = Math.max(maxDeadline, deadlines[i]);
}
PriorityQueue<Node> queue = new PriorityQueue<>(Comparator.comparingInt(node -> node.bound));
queue.offer(new Node(-1, 0, 0, 0));
int minPenalty = Integer.MAX_VALUE;
while (!queue.isEmpty()) {
Node node = queue.poll();
if (node.level == n - 1) {
minPenalty = Math.min(minPenalty, node.penalty);
continue;
}
for (int i = node.level + 1; i < n; i++) {
int newDeadline = Math.min(node.deadline, deadlines[i]);
int newPenalty = node.penalty + penalties[i] * (maxDeadline - newDeadline);
if (newPenalty < minPenalty) {
queue.offer(new Node(i, newDeadline, newPenalty, node.bound(i, newDeadline, maxDeadline, penalties)));
}
}
}
return minPenalty;
}
static class Node {
int level;
int deadline;
int penalty;
int bound;
public Node(int level, int deadline, int penalty, int bound) {
this.level = level;
this.deadline = deadline;
this.penalty = penalty;
this.bound = bound;
}
public int bound(int i, int deadline, int maxDeadline, int[] penalties) {
int penalty = this.penalty;
int remainDeadline = deadline - 1;
for (int j = i + 1; j < penalties.length; j++) {
remainDeadline = Math.min(remainDeadline, deadlines[j]);
penalty += penalties[j] * (maxDeadline - remainDeadline);
}
return penalty;
}
}
}
```
在这段代码中,我们使用一个`Node`类来表示节点,其中包括节点的层数、当前的截止时间、当前的逾期扣分和界限等信息。在`bound()`方法中,我们计算加入第`i`个作业后,剩余作业的最大截止时间和总逾期扣分。在`schedule()`方法中,我们使用一个优先队列来保存待处理的节点,并不断取出最优节点,计算其子节点,直到队列为空或界限大于当前最优解。
总之,分支界限法是一种强大的算法,可以用于解决各种最优化问题。通过Java代码的实现,我们可以更好地理解该算法的原理与实现方式。