Color Knapsack Floak Intern Solution

Color Knapsack Floak Intern Solution

  September 24, 2018    

---

Problem:

You are given N stones, labeled from 1 to N. The i-th stone has the weight W[i]. There are M colors, labeled by integers from 1 to M. The i-th stone has the color C[i] (of course, an integer between 1 to M, inclusive). You want to fill a Knapsack with these stones. The Knapsack can hold a total weight of X. You want to select exactly M stones; one of each color. The sum of the weights of the stones must not exceed X. Since you paid a premium for a Knapsack with capacity X (as opposed to a Knapsack with a lower capacity), you want to fill the Knapsack as much as possible.

Write a program that takes all the above values as input and calculates the best way to fill the Knapsack – that is, the way that minimizes the unused capacity. Output this unused capacity. See the explanation of the sample test cases for clarity.

Input :
The first line of input contains the integer T, the number of test cases. Then follows the description of T test cases. The first line of each test case contains three integers, N, M and X, separated by singlespace. The next line contains N integers, W[1], W[2], W[3] … W[N], separated by single space. The next line contains N integers C[1], C[2], C[3] … C[N], separated by single space.

Output:
 An optimal way of filling the Knapsack minimizes unused capacity. There may be several optimal ways of filling the Knapsack. Output the unused capacity of the Knapsack (a single integer on a line by itself) for an optimal way. If there is no way to fill the Knapsack, output -1. Output T lines, one for each test case.

Constraints :
1 ≤ T ≤ 10 1 ≤ M ≤ 100 M ≤ N ≤ 100 1 ≤ W[i] ≤ 100 1 ≤ C[i] ≤ M 1 ≤ X ≤ 10000

Sample Input 
4

9 3 10

2 3 4 2 3 4 2 3 4

1 1 1 2 2 2 3 3 3

9 3 10

1 3 5 1 3 5 1 3 5

1 1 1 2 2 2 3 3 3

3 3 10

3 4 4

1 2 3

3 3 10

3 3 3

1 2 1

Sample Output
0

1

-1

-1

Solution:
Hash all the stone with available costs
Recursive :
Try with all combinations and in return have minimum absolute diff with weight

DP:
dp[i][j] denotes that i stones can be taken in cost j.
Check with all Stones and if having cost<=weight then take it



Code:

import java.util.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
class colorknapsack
 {
  static int res=Integer.MAX_VALUE;
    static class FastReader
    {
        BufferedReader br;
        StringTokenizer st;

        public FastReader()
        {
            br = new BufferedReader(new
                     InputStreamReader(System.in));
        }

        String next()
        {
            while (st == null || !st.hasMoreElements())
            {
                try
                {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException  e)
                {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt()
        {
            return Integer.parseInt(next());
        }

        long nextLong()
        {
            return Long.parseLong(next());
        }

        double nextDouble()
        {
            return Double.parseDouble(next());
        }

        String nextLine()
        {
            String str = "";
            try
            {
                str = br.readLine();
            }
            catch (IOException e)
            {
                e.printStackTrace();
            }
            return str;
        }
    }

    public static int getNextdp(HashMap<Integer,ArrayList<Integer>> map,int n,int m,int w)
    {
      boolean dp[][]=new boolean[m+1][w+1];
      dp[0][0]=true;
      for(int i=1;i<=m;++i)
      {
        ArrayList<Integer>z=map.get(i);
        for(int wt:z)
        {
          for(int j=1;j<=w;++j)
          {
            if(wt<=j)
            {
              dp[i][j]|=dp[i-1][j-wt];
            }
          }
        }
      }
      for(int i=w;i>0;--i)
      if(dp[m][i])
      return w-i;
      return -1;
    }
  /*  public static void getNextRecursive(HashMap<Integer,ArrayList<Integer>> map,int n,int m,int w,int i)
    {
      if(i>m)
      {
        if(w>=0)
        res=Math.min(w,res);
        return ;
}
        ArrayList<Integer>z=map.get(i);
        for(int t:z)
        {
          if(t<=w)
          getNext(map,n,m,w-t,i+1);
        }
    }*/
 public static int knapsack(  HashMap<Integer,ArrayList<Integer>> map,int n,int m,int W)
{
if(map.size()<m)
return -1;
return getNextdp(map,n,m,W);
}
public static void main (String[] args)
{
        FastReader s=new FastReader();
        int t = s.nextInt();
while(t-->0)
{

    int n = s.nextInt();
    int m = s.nextInt();
    int W = s.nextInt();
    int c[]=new int[n];
    int w[]=new int[n];
    for(int i=0;i<n;++i)
    w[i]=s.nextInt();
    for(int i=0;i<n;++i)
    c[i]=s.nextInt();
      res=Integer.MAX_VALUE;
      HashMap<Integer,ArrayList<Integer>> map=new HashMap<>();
      for(int i=0;i<n;++i)
      {
        ArrayList<Integer>z=new ArrayList<Integer>();
        if(map.containsKey(c[i]))
        {
          z=map.get(c[i]);
        }
        z.add(w[i]);
        map.put(c[i],z);
      }
    System.out.println(knapsack(map,n,m,W));
   // System.out.println("result "+res);
}
}
}