Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.File;
- import java.io.FileNotFoundException;
- import java.util.ArrayList;
- import java.util.Scanner;
- class dpbmask{
- int [][]dptable = null;
- int tobecoveredsetsize;
- int subsetNum;
- ArrayList []subsets = null;
- int weightarray[] = null;
- ArrayList mask = null;
- int valChose;
- int valNotChose;
- dpbmask(int psize, int sub, ArrayList []a, int []w, int []bmp) {
- tobecoveredsetsize = psize;
- subsetNum = sub;
- //tobecoveredsetsize = 1<< subsetNum;
- int p = (int)Math.pow(2, (int)subsetNum);
- dptable = new int[p][subsetNum];
- for(int i=0; i<p; i++)
- {
- for(int j=0; j<subsetNum; j++)
- {
- dptable[i][j] = -1;
- }
- }
- subsets = new ArrayList[sub];
- for(int i=0; i<subsetNum; i++)
- {
- subsets[i] = new ArrayList();
- //for(int j=0; j<subsets[i].size(); j++)
- //{
- subsets[i].add(a[i]);
- //}
- }
- weightarray = new int[subsetNum];
- System.arraycopy(w, 0, weightarray, 0, subsetNum);
- mask = new ArrayList();
- for(int i=0; i<bmp.length; i++)
- {
- mask.add(bmp[i]);
- }
- }
- public int setCover(int coveredBitMask,int nowConsiderIndex){
- if(nowConsiderIndex == subsetNum && coveredBitMask != ((1<<tobecoveredsetsize)-1))
- //if(nowConsiderIndex == subsetNum && coveredBitMask != ((1<<subsetNum)-1))
- return 1000;
- else if(nowConsiderIndex == subsetNum || coveredBitMask == ((1<<tobecoveredsetsize)-1))
- //else if(nowConsiderIndex == subsetNum || coveredBitMask == ((1<<subsetNum)-1))
- return 0;
- //else if(dptable[coveredBitMask |(int) mask.get(nowConsiderIndex)][ nowConsiderIndex ] != -1)
- // return dptable[coveredBitMask | (int)mask.get(nowConsiderIndex)][ nowConsiderIndex ];
- else if(dptable[coveredBitMask][nowConsiderIndex] != -1)
- return dptable[coveredBitMask][nowConsiderIndex];
- else{
- valChose = setCover(coveredBitMask | (int) mask.get(nowConsiderIndex), nowConsiderIndex+1)+ weightarray[nowConsiderIndex];
- System.out.println("Valu chosen: " + valChose);
- valNotChose = setCover(coveredBitMask, nowConsiderIndex+1);
- System.out.println("Valu Not chosen: " + valNotChose);
- dptable[coveredBitMask][nowConsiderIndex] = Math.min(valChose, valNotChose);
- }
- System.out.println(".........");
- System.out.println("Valu chosen: " + valChose);
- System.out.println("Valu Not chosen: " + valNotChose);
- showdptable();
- System.out.println(".........");
- return dptable[coveredBitMask][nowConsiderIndex];
- }
- public void show(){
- System.out.println("printing from the class: ");
- System.out.println("Parent Set Size: "+ tobecoveredsetsize);
- System.out.println("Sub set Number: " + subsetNum);
- System.out.println("Subsets: ");
- for(int i=0; i<subsetNum; i++)
- {
- //for(int j=0; j<subsets[i].size(); j++)
- //{
- System.out.print(subsets[i]);
- //}
- System.out.println();
- }
- System.out.println("bitmasks are: ");
- for(int i=0; i< mask.size(); i++)
- System.out.print(mask.get(i) + " ");
- System.out.println();
- System.out.println("Weights are: ");
- for(int i=0; i<weightarray.length; i++)
- System.out.print(weightarray[i] + " ");
- System.out.println();
- }
- public void showdptable()
- {
- for(int i=0; i<dptable.length; i++)
- {
- for(int j=0; j<dptable[i].length; j++)
- {
- System.out.print(dptable[i][j] + " ");
- }
- System.out.println();
- }
- }
- }
- public class dpbitmask {
- public static void main(String[] args) throws FileNotFoundException {
- // TODO code application logic here
- Scanner fileScanner = new Scanner(new File("J:\\CSE 462 ALGORITHIM ENGINEERING SESSIONAL\\dpBitmask\\src\\input.txt"));
- int parentsetsize = fileScanner.nextInt();
- int noofsubset = fileScanner.nextInt();
- System.out.println(parentsetsize + " " + noofsubset);
- ArrayList []al = new ArrayList[noofsubset];
- for(int i=0; i<noofsubset; i++)
- {
- int noofelem = fileScanner.nextInt();
- al[i] = new ArrayList();
- for(int j=0; j<noofelem; j++)
- {
- al[i].add(fileScanner.nextInt());
- }
- }
- System.out.println("Subsets are: ");
- for(int i=0; i<noofsubset; i++)
- {
- for(int j=0; j<al[i].size(); j++)
- {
- System.out.print(al[i].get(j));
- }
- System.out.println();
- }
- System.out.println("bitmasks are: ");
- int []bitmaskpattern = new int[noofsubset];
- for(int i=0; i<bitmaskpattern.length; i++)
- {
- bitmaskpattern[i] = 0;
- }
- for(int i=0; i<noofsubset; i++)
- {
- for(int j=0; j<al[i].size(); j++)
- {
- bitmaskpattern[i] = bitmaskpattern[i] | (1 << (int) al[i].get(j));
- }
- }
- for(int i=0; i<bitmaskpattern.length; i++)
- {
- System.out.println(bitmaskpattern[i]);
- }
- int []weight = new int[noofsubset];
- for(int i=0; i<noofsubset; i++)
- {
- weight[i] = fileScanner.nextInt();
- }
- System.out.println("Weights are: ");
- for(int i=0; i<weight.length; i++)
- {
- System.out.print(weight[i] + " ");
- }
- System.out.println();
- System.out.println("++++++++++++++++++++++");
- dpbmask d = new dpbmask(parentsetsize, noofsubset, al, weight, bitmaskpattern);
- d.show();
- System.out.println("++++++++++++++++++++++");
- //d.setCover(noofsubset, noofsubset)
- //d.showdptable();
- int set = d.setCover(0, 0);
- System.out.println("++++++++++++++++");
- System.out.println(set);
- //d.showdptable();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement