Write a program that solves the Subset Sum Problem for the following sets: Set A

Question

Write a program that solves the Subset Sum Problem for the following

sets: Set A: {-7, -3, -2, 5, 8}

Set B: {6, 5, 3, 1, 8, 7, 2, 4, -2, -3}

For each set, record the start time and end time for the solution.

Modify your program to solve the Subset Sum Problem for Set C that includes a random number of integers (20 >= n <= 100), with each value ranging from -10 to 10. In other words, the size of the set will be a random number from 20 to 100 inclusive, with each element in the set being a random number from -10 to 10 inclusive.

Run the Subset Sum Problem 3 times for Set C and record the start and end time for the solution.

Note: Your code may not halt (i.e., welcome to the Halting Problem), so you should have a mechanism to end your code when this occurs.

Explanation / Answer

// code version 1.0:

/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
package subset1;

/**
*
* @author Admin
*/
public class SubSet1 {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
      
        int [] setA = {-7, -3, -2, 5, 8};
        int [] setB = {6, 5, 3, 1, 8, 7, 2, 4, -2, -3};
        boolean subSet = true;
        int i, j;
        for ( i = 0; i<setA.length; i++)    {
            for (j = 0; j<setB.length; j++ )   {
                if (setA[i] == setB[j]) break;
                if (j == (setB.length - 1) ) subSet = false;
            } // end for j
            if (subSet == false) break;
        } // end for i
        System.out.println("Subset status = " + (subSet) );
    } // end main
  
  
  
} // end public class

run:
Subset status = false
BUILD SUCCESSFUL (total time: 4 seconds)

/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
package subset1;
import java.util.Random;

/**
*
* @author Admin
*/
public class SubSet1 {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
        long beginTm = System.currentTimeMillis();
        int [] setA = {-7, -3, -2, 5, 8};
        int [] setB = {6, 5, 3, 1, 8, 7, 2, 4, -2, -3};
        boolean subSet = true;
        int i, j;
        for ( i = 0; i<setA.length; i++)    {
            for (j = 0; j<setB.length; j++ )   {
                if (setA[i] == setB[j]) break;
                if (j == (setB.length - 1) ) subSet = false;
            } // end for j
            if (subSet == false) break;
        } // end for i
        System.out.println("Subset status = " + (subSet) );
        int [] setC = new int[85];
        Random r1 = new Random();
        int n=0; // from 20 to 100
        int value = 0; // from -10 to 10
        n = r1.nextInt(100) + 20;
        for (i=0; i<n; i++)    {
            value = r1.nextInt(10)+ -10;
            setC[i] = value;
        } // end for
        System.out.println("Set C = " + setC);
          
        long elapsedTm = System.currentTimeMillis() - beginTm;
        System.out.println("Time taken = " + (elapsedTm) );
      
    } // end main
  
  
  
} // end public class

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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