1
2
3
4
6,
2,5,7,10,5,2,
3,8,4,11,3,4,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
package task_scheduling;

import java.io.IOException;
import java.util.ArrayList;
import java.util.List;

public class Main {

	private final static int SIZE = 50;
	private final static int MAXINT = 999;

	/** 任务 */
	private static TaskBean taskA;
	private static TaskBean taskB;

	public static void main(String[] args) throws IOException {

		int data;

		ReadFile();

		int temp = TaskScheduling.TaskScheduling(taskA, taskB);

		if (0 == temp) {
			System.out.println("计算出错");
		} else {

			// out.txt
			FileUtil.writeFile("output.txt", temp + "");
		}
	}

	/**
	 * Read input.txt
	 * 
	 * @throws IOException
	 */
	private static void ReadFile() throws IOException {

		int[] Data = new int[SIZE];// 文件读取到的数据转换为int存储
		String[] Data_str = new String[SIZE];// 文件读取到的数据

		Data_str = FileUtil.readFile("input.txt").split("\,");

		int index = 0;
		for (String item : Data_str) {

			Data[index++] = Integer.parseInt(item);
		}

		int N = (int) Data[0];
		int[] a = new int[SIZE], b = new int[SIZE];
		for (int i = 1; i <= N; i++) {
			a[i] = Data[i];
		}
		for (int i = 1, j = N + 1; j <= 2 * N; j++, i++) {
			b[i] = Data[j];
		}

		taskA = new TaskBean(N, a);
		taskB = new TaskBean(N, b);
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
package task_scheduling;

public class TaskBean {

	private final int SIZE = 50;// 数组大小
	private final int MAXINT = 999;

	private int N;// 任务数量
	private int[] task = new int[SIZE];// 处理机处理任务的时间

	// 存储的计算后的数据
	private int[] Sum = new int[SIZE];// 处理到第i个作业累加的时间和
	private int tempSum = 0;// 和

	public TaskBean(int N, int[] task) {
		this.setN(N);
		this.setTask(task);

		for (int i = 1; i <= N; i++) {
			tempSum += task[i];
			Sum[i] = tempSum;
		}
	}

	public int getN() {
		return N;
	}

	public void setN(int n) {
		N = n;
	}

	public int[] getTask() {
		return task;
	}

	public void setTask(int[] task) {
		this.task = task;
	}

	public int[] getSum() {
		return Sum;
	}

	public void setSum(int[] sum) {
		Sum = sum;
	}

	public int getTempSum() {
		return tempSum;
	}

	public void setTempSum(int tempSum) {
		this.tempSum = tempSum;
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
package task_scheduling;

/**
 * 独立任务最优调度问题
 * 
 * @author luo
 *
 */
public class TaskScheduling {

	private final static int SIZE = 50;
	private final static int MAXINT = 999;// 无穷大

	public static int TaskScheduling(TaskBean taskA, TaskBean taskB) {
		int temp = 0;// 返回的数
		int N = taskA.getN();// 任务数
		int[] SumA = taskA.getSum();
		int[] SumB = taskB.getSum();
		int[] a = taskA.getTask();
		int[] b = taskB.getTask();
		// a的和、b的和min
		int MinSum = (taskB.getTempSum() > taskA.getTempSum()) ? taskA.getTempSum() : taskB.getTempSum();


		/// 动态二维数组
		int[] MaxTime = new int[MinSum + 1];
		int[][] F = new int[SIZE][N + 1];
		// 初始化
		SumB[0] = 0;
		for (int i = 0; i < N + 1; i++) {
			F[i] = new int[MinSum + 1];
			F[i][0] = SumB[i];// SumB[0]没赋值，调试时会输出地址
			for (int j = 1; j <= MinSum; j++) {
				F[i][j] = 0;
			}
		}
		// 计算F矩阵
		for (int k = 1; k <= N; k++) {
			temp = (SumA[k] > SumB[k]) ? SumB[k] : SumA[k];
			for (int x = 1; x <= temp; x++) { // A最多用AB前k任务的最小值，如果B最少就全用B做。
				if (x >= a[k])// 等于号不能少
					F[k][x] = (F[k - 1][x] + b[k] < F[k - 1][x - a[k]]) ? F[k - 1][x] + b[k] : F[k - 1][x - a[k]];
				else
					F[k][x] = F[k - 1][x] + b[k];
			}
		}

		temp = MAXINT;
		//得出最优调度
		for (int i = 0; i <= MinSum; i++) {
			MaxTime[i] = (i > F[N][i]) ? i : F[N][i];
			if (temp > MaxTime[i])
				temp = MaxTime[i];
		}

		return temp;
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
package task_scheduling;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.UnsupportedEncodingException;

public class FileUtil {

	/**
	 * 读文件 返回字符串
	 * @param url
	 *            文件地址，如："/sdcard/test.txt"
	 * @return
	 * @throws IOException 
	 */
	public static String readFile(String url) throws IOException {
		// 读取
		String str = ""; // 读取到的内容
		File urlFile = new File(url);
		InputStreamReader isr = new InputStreamReader(new FileInputStream(urlFile), "UTF-8");
		BufferedReader br = new BufferedReader(isr);

		String mimeTypeLine = null;
		while ((mimeTypeLine = br.readLine()) != null) {
			str = str + mimeTypeLine;
		}
		System.out.println("FileUtil读取内容：" + str);
		return str;
	}
	/**
	 * 写文件，成功返回true
	 * @param filePath 文件地址
	 * @param sourceString 待写入字符串
	 * @return
	 */
	public static boolean writeFile(String filePath, String sourceString){
		//写入
		try{
			System.out.println("写入文件信息：" + sourceString);
			byte[] sourceByte = sourceString.getBytes();  
			if(null != sourceByte){  
			        File file = new File(filePath);     //文件路径（路径+文件名）  
			        if (!file.exists()) {   //文件不存在则创建文件，先创建目录  
			         
			            file.createNewFile();  
			        }  
			        FileOutputStream outStream = new FileOutputStream(file);    //文件输出流用于将数据写入文件  
			        outStream.write(sourceByte);  
			        outStream.close();  //关闭文件输出流  
			}  
		}catch(Exception e){
			System.out.println("写入失败");
			return false;
		}
		System.out.println("写入成功");
		return true;
	}
}