在Java中作业调度问题 [英] Job Scheduling Problem in Java
问题描述
我写一个要解决的问题工作时间表，但我有一个很难理解怎么样。
本木店已经为它的世界著名的摇椅（每1阶主持）的订单积压。有几个 参与制作手工巴伯摇椅步骤（如切割木块，组装，打磨，将一个污点， 并应用清漆）。
，使椅子所需的总时间为1周。然而，由于椅子都在不同的售 地区和不同的市场，利润为每个订单的金额可能会有所不同。此外，还有一个相关联的最后期限 与每个订单。该公司将只赚取利润，如果他们赶上最后期限;否则，利润为0。
编写一个程序，将确定最佳时间表的订单，将利润最大化。将输入文件 含有一个或多个测试用例。在测试用例的第一行包含一个整数N（O N 1000），即再presents的 被挂单的数量。
0对于n的值表示的输入文件的末尾。 接下来的n行包含每3正整数。第一个整数，我，是一个订单号。
对于给定的所有订单号 测试用例是独一无二的。再$ P $第二个整数psents周数从现在到最后期限我 日 订购。该 再$ P $第三个整数psents的利润，该公司将获得如果最后期限是满足了我的额 日 顺序。
我所要求的是我应该怎么去解决这个问题的算法。
有关每个测试用例在输入文件中，输出文件应该输出，报告的利润而导致的量的线 在最佳顺序完成订单。
例输入文件（sched.in）
7
1 3 40
2 1 35
3 1 30
4 3 25
5 1 20
6 3 15
7 2 10
4
3054 2 30
4099 1 35
3059 2 25
2098 1 40
0
示例输出文件（sched.out）
100
70
你的问题的假设是不完整的。这是需要知道豪很多椅子，你可以每周做。也许你可以一次让所有。但是让我们假设你只能让一个。解决的办法是这样的。
根据卡梅伦斯金纳的非常聪明的意见我改变我的答案是：
公共类利亚
{
名单＆LT;输入＆GT; DATAS =新的ArrayList＆LT;输入＆GT;（）;
级输入
{
公众诠释的利润;
公众诠释的最后期限;
公众诠释指数1;
公众诠释索引2;
公众诠释总和（）{返回索引1 +索引2;}
/ **
* @参数利润
* @参数的最后期限
* /
公众的意见（INT的最后期限，INT利润）
{
超（）;
this.profit =利润;
this.deadline =期限;
}
}
公共无效readData1（）
{
this.datas.add（新的输入（1,1））;
this.datas.add（新的输入（1,1））;
this.datas.add（新的输入（1,1））;
this.datas.add（新的输入（1,1））;
this.datas.add（新的输入（1,1））;
this.datas.add（新的输入（1,1））;
this.datas.add（新的输入（1,1））;
this.datas.add（新的输入（1,1））;
this.datas.add（新的输入（1,1））;
this.datas.add（新的输入（1,1））;
this.datas.add（新的输入（10,1000））;
this.datas.add（新的输入（10,1000））;
this.datas.add（新的输入（10,1000））;
this.datas.add（新的输入（10,1000））;
this.datas.add（新的输入（10,1000））;
this.datas.add（新的输入（10,1000））;
this.datas.add（新的输入（10,1000））;
this.datas.add（新的输入（10,1000））;
this.datas.add（新的输入（10,1000））;
this.datas.add（新的输入（10,1000））;
}
公共无效readData2（）
{/ *
3 40
2 1 35
3 1 30
4 3 25
5 1 20
6 3 15
7 2 10 * /
this.datas.add（新的输入（3,40））;
this.datas.add（新的输入（1,35））;
this.datas.add（新的输入（1,30））;
this.datas.add（新的输入（3,25））;
this.datas.add（新的输入（1,20））;
this.datas.add（新的输入（3,15））;
this.datas.add（新的输入（2,10））;
}
公共无效readData3（）
{/ *
2 30
4099 1 35
3059 2 25
2098 1 40 * /
this.datas.add（新的输入（2,30））;
this.datas.add（新的输入（1,35））;
this.datas.add（新的输入（2,25））;
this.datas.add（新的输入（1,40））;
}
@燮pressWarnings（未登记）
公共无效sortbyprofit（名单＆LT;输入＆GT; DATAS）
{
Collections.sort（DATAS，新的比较（）{
公众诠释比较（对象01，对象02）
{
如果（（（输入）（01））的利润及所述;（（输入）（02））的利润）
返回1;
否则，如果（（（输入）（01））。利润==（（输入）（02））。利润）
返回0;
否则返回-1;
}}）;
}
@燮pressWarnings（未登记）
公共无效sortbydeadline（名单＆LT;输入＆GT; DATAS）
{
Collections.sort（DATAS，新的比较（）{
公众诠释比较（对象01，对象02）
{
如果（（（输入）（01））的最后期限＆GT;（（输入）（02））的最后期限）
返回1;
否则如果（（（输入）（01））。限期==（（输入）（02））。最后期限）
返回0;
否则返回-1;
}}）;
}
@燮pressWarnings（未登记）
公共无效sortbySum（名单＆LT;输入＆GT; DATAS）
{
Collections.sort（DATAS，新的比较（）{
公众诠释比较（对象01，对象02）
{
如果（（（输入）（01））和（）＆GT;（（输入）（02））和（））
返回1;
否则如果（（（输入）（01））。总和（）==（（输入）（02））。总和（））
返回0;
否则返回-1;
}}）;
}
@燮pressWarnings（未登记）
公共静态无效的主要（字串[] args）
{
利亚啧=新利亚（）;
//tsk.readData1（）;
//tsk.readData2（）;
tsk.readData3（）;
而（tsk.datas.size（）大于0）
{
//排序利润
tsk.sortbyprofit（tsk.datas）;
INT IDX0 = 1;
//分配指标
对于（输入数据：tsk.datas）
{
data.index1 = IDX0;
IDX0 ++;
}
//排序最后期限
tsk.sortbydeadline（tsk.datas）;
INT IDX2 = 1;
对于（输入数据：tsk.datas）
{
data.index2 = IDX2;
IDX2 ++;
}
//排序之和利润
tsk.sortbySum（tsk.datas）;
名单＆LT;输入＆GT; tmpdatas =新的ArrayList＆LT;输入＆GT;（）;
INT valsum = tsk.datas.get（0）.SUM（）;
对于（输入数据：tsk.datas）
{
如果（data.sum（）== valsum）
tmpdatas.add（数据）;
}
tsk.sortbyprofit（tmpdatas）;
//获取第一个作为结果
输入海图= tmpdatas.get（0）;
的System.out.println（结果===＆gt;中+ thedata.profit）;
tsk.datas.remove（海图）;
tmpdatas =新的ArrayList＆LT;输入＆GT;（）;
对于（输入数据：tsk.datas）
{
data.deadline--;
如果（data.deadline大于0）
tmpdatas.add（数据）;
}
tsk.datas = tmpdatas;
}
}
}
I am writing a problem to solve Job schedules but I am having a hard time understanding how.
The Wood Shop has a backlog of orders for its world famous rocking chair (1 chair per order). There are several steps involved in making a handmade Baber Rocking chair (eg. cutting wood pieces, assembly, sanding, applying a stain, and applying varnish).
The total time required to make a chair is 1 week. However, since the chairs are sold in different regions and various markets, the amount of profit for each order may differ. In addition, there is a deadline associated with each order. The company will only earn a profit if they meet the deadline; otherwise, the profit is 0.
Write a program that will determine an optimal schedule for the orders that will maximize profit. The input file will contain one or more test cases. The first line in a test case will contain an integer, n (0 n 1000), that represents the number of orders that are pending.
A value of 0 for n indicates the end of the input file. The next n lines contain 3 positive integers each. The first integer, i, is an order number.
All order numbers for a given test case are unique. The second integer represents the number of weeks from now until the deadline for i th order. The third integer represents the amount of profit that the company will earn if the deadline is met for the i th order.
What I am asking for is an algorithm of how I should go about solving this problem.
For each test case in the input file, the output file should output a line that reports the amount of profit that results from completing the orders in an optimal order.
Example Input File (sched.in)
7
1 3 40
2 1 35
3 1 30
4 3 25
5 1 20
6 3 15
7 2 10
4
3054 2 30
4099 1 35
3059 2 25
2098 1 40
0
Example Output File (sched.out)
100
70
The postulate of your problem is incomplete. It is required to know ho many chairs can you make per week. Maybe you can make all at once. But let's assume you can make only one. The solution is like this.
based on the very smart comments of Cameron Skinner I change my answer to this:
public class tarea
{
List<input> datas = new ArrayList<input>();
class input
{
public int profit;
public int deadline;
public int index1;
public int index2;
public int sum() {return index1+index2;}
/**
* @param profit
* @param deadline
*/
public input(int deadline, int profit)
{
super();
this.profit = profit;
this.deadline = deadline;
}
}
public void readData1()
{
this.datas.add(new input(1,1));
this.datas.add(new input(1,1));
this.datas.add(new input(1,1));
this.datas.add(new input(1,1));
this.datas.add(new input(1,1));
this.datas.add(new input(1,1));
this.datas.add(new input(1,1));
this.datas.add(new input(1,1));
this.datas.add(new input(1,1));
this.datas.add(new input(1,1));
this.datas.add(new input(10,1000));
this.datas.add(new input(10,1000));
this.datas.add(new input(10,1000));
this.datas.add(new input(10,1000));
this.datas.add(new input(10,1000));
this.datas.add(new input(10,1000));
this.datas.add(new input(10,1000));
this.datas.add(new input(10,1000));
this.datas.add(new input(10,1000));
this.datas.add(new input(10,1000));
}
public void readData2()
{/*
3 40
2 1 35
3 1 30
4 3 25
5 1 20
6 3 15
7 2 10 */
this.datas.add(new input(3,40));
this.datas.add(new input(1,35));
this.datas.add(new input(1,30));
this.datas.add(new input(3,25));
this.datas.add(new input(1,20));
this.datas.add(new input(3,15));
this.datas.add(new input(2,10));
}
public void readData3()
{/*
2 30
4099 1 35
3059 2 25
2098 1 40*/
this.datas.add(new input(2,30));
this.datas.add(new input(1,35));
this.datas.add(new input(2,25));
this.datas.add(new input(1,40));
}
@SuppressWarnings("unchecked")
public void sortbyprofit(List<input> datas)
{
Collections.sort(datas, new Comparator() {
public int compare(Object o1, Object o2)
{
if(((input)(o1)).profit < ((input)(o2)).profit)
return 1;
else if(((input)(o1)).profit == ((input)(o2)).profit)
return 0;
else return -1;
}});
}
@SuppressWarnings("unchecked")
public void sortbydeadline(List<input> datas)
{
Collections.sort(datas, new Comparator() {
public int compare(Object o1, Object o2)
{
if(((input)(o1)).deadline > ((input)(o2)).deadline)
return 1;
else if(((input)(o1)).deadline == ((input)(o2)).deadline)
return 0;
else return -1;
}});
}
@SuppressWarnings("unchecked")
public void sortbySum(List<input> datas)
{
Collections.sort(datas, new Comparator() {
public int compare(Object o1, Object o2)
{
if(((input)(o1)).sum() > ((input)(o2)).sum())
return 1;
else if(((input)(o1)).sum() == ((input)(o2)).sum())
return 0;
else return -1;
}});
}
@SuppressWarnings("unchecked")
public static void main(String[] args)
{
tarea tsk = new tarea();
//tsk.readData1();
//tsk.readData2();
tsk.readData3();
while (tsk.datas.size() > 0)
{
//sort by profit
tsk.sortbyprofit(tsk.datas);
int idx0 = 1;
//assign index
for (input data : tsk.datas)
{
data.index1 = idx0;
idx0++;
}
//sort by deadline
tsk.sortbydeadline(tsk.datas);
int idx2 = 1;
for (input data : tsk.datas)
{
data.index2 = idx2;
idx2++;
}
//sort by sum and profit
tsk.sortbySum(tsk.datas);
List<input> tmpdatas = new ArrayList<input>();
int valsum = tsk.datas.get(0).sum();
for (input data : tsk.datas)
{
if (data.sum() == valsum)
tmpdatas.add(data);
}
tsk.sortbyprofit(tmpdatas);
//get the first one as result
input thedata = tmpdatas.get(0);
System.out.println("result ===> " + thedata.profit);
tsk.datas.remove(thedata);
tmpdatas = new ArrayList<input>();
for (input data : tsk.datas)
{
data.deadline--;
if (data.deadline > 0)
tmpdatas.add(data);
}
tsk.datas = tmpdatas;
}
}
}
这篇关于在Java中作业调度问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
