The Weighted Interval Scheduling problem is this: Given a set of weighted interv

Question

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.

A weighted interval x can be represented by a triple

       x = (s, f, v),

where

      s = start time of x,    f = finish time of x,   v = weight or value of x

For example, consider the test case for Weighted Interval Scheduling problem depicted below:

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

The program MUST use recursion. An iterative solution will not receive full credit. Use of memoization will receive 20 points extra credit.

it is jave course, i hope u can give a specific code, thanks.

Explanation / Answer

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Arrays;
import java.util.Scanner;
import java.awt.*;
import javax.swing.*;

public class weighted extends JFrame {

   public void showImage() {
       JFrame frame = new JFrame("Interval");
       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 = "weighted.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) + " " + Arrays.toString(M));
      
       JOptionPane.showMessageDialog(null, "Optimal Value: " + p[7]);
       //JOptionPane.showMessageDialog(null, "Optimal Value: " + p[7]);
      
       weighted show1 = new weighted();
       show1.showImage();
   }

}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.