利润最大化，作业调度

Question

我有一个场景，每个时间段都有利润和多个工作可供选择。我需要 select 每个时间段的工作，以便获得整体最大利润。我要的是获得的最大利润和进度表。

我唯一能想到的就是尝试使用暴力破解每个组合。我怎样才能解决这个问题 effectively.Is 我可以通过使用特定的算法或数据结构来更好地解决这个问题吗？

在下面的示例中，任何作业 J1、J2、J4 都可以为时间段 1 select编辑。同样，对于其他时间段，可以 select 编辑任何一个或 none 个作业。对于特定时间段，只能 select 编辑一项工作。如果一项工作在一个时间段内完成，则无法再次完成。

例如。如果j1在TS1中完成，则无法在TS2中再次拾取

+----------+--------+----------------------+
| TimeSlot | Profit | Possible Job         |
+----------+--------+----------------------+
|        1 |     50 | J1 or J2 or J4       |
|        2 |    100 | J1                   |
|        3 |     20 | J2                   |
|        4 |     60 | J5 or J4             |
|        5 |     15 | J1 or J2 or J3 or J6 |
+----------+--------+----------------------+

Answer 1

这可以通过weighted maximum matching in bipartite graph最佳解决。

在这里，您的图表是 G=(U,V,E)，其中：

U = {1, 2, ...., n} // time slots
V = {J1, J2, ..., J_m} // jobs
E = { (i,J) | if job J can be done in time i }
w(i,J) = profit(i)

上图中的最大匹配直接转化为最优解，通过在时间段i中执行任务J当且仅当最大匹配节点J与节点i.

Answer 2

public class JobProfitMaximizer {

private int numberOfJobs;
private Job[] jobs;
private int maxProfit;

public class JobComparator implements Comparator<Job> {

    @Override
    public int compare(Job arg0, Job arg1) {
        if (arg0.end <= arg1.end)
            return -1;
        else
            return 1;
    }
}

public JobProfitMaximizer() {
    numberOfJobs = 0;
    maxProfit = 0;
}

private void printJobProfiles() {
    for (Job j : jobs) {
        System.out.println(j.start + " " + j.end + " " + j.profit);
    }
}

private void createJobProfiles() {
    jobs = new Job[numberOfJobs];
    File inputFile = new File("***Filepath***********");
    Scanner sc = null;
    int jobCounter = 0;
    try {
        sc = new Scanner(inputFile);
        while (sc.hasNextLine()) {
            String s = sc.nextLine();
            String[] profileOfJob = s.split(" ");
            int start = Integer.parseInt(profileOfJob[1]);
            int end = Integer.parseInt(profileOfJob[2]);
            int profit = Integer.parseInt(profileOfJob[3]);
            jobs[jobCounter] = new Job(start, end, profit);
            jobCounter = jobCounter + 1;
        }
    } catch (FileNotFoundException e) {
        System.out.println("The file is not present");
    } finally {
        try {
            if (sc != null)
                sc.close();
        } catch (Exception f) {
            System.out.println(f.getMessage());
        }
    }
}

private void setNumberOfJobs() {
    File inputFile = new File("***Filepath***********");
    Scanner sc = null;
    int countOfJobs = 0;
    try {
        sc = new Scanner(inputFile);
        while (sc.hasNextLine()) {
            countOfJobs = countOfJobs + 1;
            sc.nextLine();
        }
        numberOfJobs = countOfJobs;
        System.out.println(numberOfJobs);
    } catch (FileNotFoundException e) {
        System.out.println("The file is not present");
    } finally {
        try {
            if (sc != null)
                sc.close();
        } catch (Exception f) {
            System.out.println(f.getMessage());
        }
    }
}

private void sortJobsOnFinishTimes() {
    JobComparator jc = new JobComparator();
    Arrays.sort(jobs, jc);
}

private void calculateMaximumProfit() {
    int[] T = new int[numberOfJobs];
    T[0] = jobs[0].profit;

    for (int i = 1; i < numberOfJobs; i++) {
        T[i] = Math.max(T[i - 1], jobs[i].profit);
        for (int j = i - 1; j >= 0; j--) {
            if (jobs[j].end <= jobs[i].start) {
                T[i] = Math.max(T[i], T[j] + jobs[i].profit);
                break;
            }
        }
    }

    int currentMaxProfitValue = T[0];

    for (int m : T) {
        if (m > currentMaxProfitValue) {
            currentMaxProfitValue = m;
        }
    }
    maxProfit = currentMaxProfitValue;
}

public static void main(String args[]) {
    JobProfitMaximizer j = new JobProfitMaximizer();
    j.setNumberOfJobs();
    j.createJobProfiles();
    j.sortJobsOnFinishTimes();
    j.calculateMaximumProfit();
    System.out.println("The maximum profit is " + j.maxProfit);
}

}

利润最大化，作业调度

Maximise the profit, Job scheduling

java

algorithm

graph

greedy