dp

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;
        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))
            return 1000;

        else if(nowConsiderIndex == subsetNum || coveredBitMask == ((1<<tobecoveredsetsize)-1))
            return 0;
        else if(dptable[coveredBitMask |(int) mask.get(nowConsiderIndex)][ nowConsiderIndex ] != -1)
            return dptable[coveredBitMask | (int)mask.get(nowConsiderIndex)][ 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();
    }
}