Thread: Java Weighted interval scheduling

the Weighted Interval Scheduling problem is this: Given a set of weighted
intervals, choose a set of non-overlapping intervals such that the total weight
is maximal.

These weighted intervals can be represented by the triples
(0,3,3) (1,4,2) (0,5,4) (3,6,1) (4,7,2) (3,9,5) (5,10,2) (8,10,1)
Write a program to compute a solution to the Weighted Interval Scheduling
problem.
Your program must read in a set of weighted intervals. Each interval should
be entered as 3 integers. The intervals must be given in a textfile and also be
entered in increasing order of finish time. In the above case we would have
0 3 3 1 4 2 0 5 4 3 6 1 ...
The program should print out the value of the total weight of the optimum
solution and the indices of the selected intervals. In the above case, the output
would be something like (this output is NOT correct)
Optimum value: 7
Interval Sequence: 2 5


My text file is here: http://www.filedropper.com/weightedintervals

pic: http://i.imgur.com/D6fcq.jpg

I will have it to my box account soon. I can upload a archive file for eclipse if that helps you help me.

My code as of right now always shows 8. Even if thats not the best solution.

I need to print out the best job numbers also... the picture im displaying is the chart im going off of. Ill attach it... I want to take the jpanes and put them into a text box in the GUI. Its due thursday BTW!



Here is my code so far:

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Arrays;
import java.util.Scanner;
import java.awt.*;
import javax.swing.*;
 
public class weightedIntervals extends JFrame {
 
	public void showImage() {
		JFrame frame = new JFrame("My GUI");
		frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
		frame.setSize(700, 400);
		frame.setResizable(false);
		frame.setLocationRelativeTo(null);
 
		// Inserts the image icon
		String imgStr = "Capture.jpg";
 
		ImageIcon image = new ImageIcon(imgStr);
		JLabel label1 = new JLabel(" ", image, JLabel.CENTER);
		frame.getContentPane().add(label1);
 
		frame.validate();
		frame.setVisible(true);
 
	}
 
	public static void main(String[] args) throws FileNotFoundException {
		int i, j;
		String FileName;
		FileName = "weightedIntervals.txt";
		File f = new File(FileName);
		Scanner fileIn = new Scanner(f);
		int[] Start = new int[100];
		int[] Finish = new int[100];
		int[] Weight = new int[100];
		i = 0;
		while (fileIn.hasNext()) {
			Start[i] = fileIn.nextInt();
			Finish[i] = fileIn.nextInt();
			Weight[i] = fileIn.nextInt();
			i++;
		}
		i = 0;
		while (i < 9) {
			//System.out.println(Start[i] + ", " + Finish[i] + ", " + Weight[i]);
			i++;
		}
		// just input
		int Jobs[] = new int[8];
		j = 0;
		i = 0;
		while (i != 7) {
			Jobs[i] = i;
			i++;
		}
 
		int M[] = new int[8];
		int p[] = new int[8];
 
		i = 0;
		j = 0;
		while (j != 8) {
			i = 0;
			while (i != 8) {
				if (Start[j] >= Finish[i]) {
					p[j] = Math.max(Finish[i], Start[j]);
				}
				i++;
			}
			j++;
		}
 
		j = 0;
		while (j <= 7) {
			if (j == 0) {
				M[j] = 0;
			}
			if (j > 0) {
				M[j] = Math.max(Weight[j] + Weight[p[j]], M[j - 1]);
			}
			j++;
		}
 
		JOptionPane.showMessageDialog(null,Arrays.toString(p) + "\n" + Arrays.toString(M));
 
		JOptionPane.showMessageDialog(null, "Optimal Value: " + p[7]);
		//JOptionPane.showMessageDialog(null, "Optimal Value: " + p[7]);
 
		weightedIntervals show1 = new weightedIntervals();
		show1.showImage();
	}
 
}

I could also post an archive of my eclipse file if that helps