Troop selection algorithm

This question was asked at TCS Code Vita round 2 which found it really interesting.

Question:
There are various troops (for e.g. Barbarian, Archer, Giant, Goblin and so on) which belong to some category C (for e.g. Elixir Troop, Temporary Troop, Super Troops and so on).

To train them you decided to have a versatile army where you select at most one or no troops from each category of the troops such that it has maximum damage per second and the troops fit within the barrack size for training.
Constraints

Length of S = D = C

1 <= length of S, D <= 100

1 <= Number of categories <= 20

1 <= B <= Sum of S

Size of the troop <= Size of the Barrack i.e. Si <= B
Input

The first line contains the list of integers denoting damage per second capability Di of the troop.

The second line contains the list of integers denoting the size Si of the troop.

The third line contains a list of integers denoting the category Ci of the troop.

Last line contains an integer denoting the size of the barrack.
Output

Print the maximum damage per second that can be achieved.
Time Limit (secs)

1
Examples

Example 1

Input

8 9 4 9 1 8 1 5 6 8

2 5 7 2 3 4 5 9 3 8

4 2 2 3 4 3 2 1 2 1

Output

Explanation

The goal is to maximize the damage per second where you select at most one or none from each category. So here we choose the 1st troop which belongs to category 4, 2nd troop which belongs to category 2 and 4th troop which belongs to category 3 whose total size is 9 which is within the barrack size. We could not accommodate any troop from category 1 because the damage per second capability reduces or the barrack capacity falls short. Hence, the total damage per second is 26.

Code (in java):


import java.util.*;
 public class Coc {
     public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int n = 10;
        List<Integer> damage = new ArrayList<>();
        List<Integer> size = new ArrayList<>();
        List<Integer> category = new ArrayList<>();
        System.out.println("Enter details: ");
        for (int i = 0; i < n; i++) {
            damage.add(sc.nextInt());
            size.add(sc.nextInt());
            category.add(sc.nextInt());
        }

        int barrackSize = sc.nextInt();

        System.out.println(barrackSize);
        sc.close();
        List<Integer> brkList = new ArrayList<>();

        int best;
        for(int j = 0;j<barrackSize ; j++){
            //calling fucntion
            best = justify(category.get(j), category, size);
            brkList.add(best);
            if(barrackSize >= size.get(best) ){
                barrackSize -=  size.get(best);
                category.remove(best);
                size.remove(best);
            }
        }
        //Now we got the indexes which makes the perfect combination
        int totdmg = 0;
        for (int k = 0; k<brkList.size();k++){
            totdmg += damage.get(k);
        }
        System.err.println(totdmg + " ");

    }

    public static int justify(int cat, List<Integer> catList, List<Integer> sizeList) {
        List<Integer> iList = new ArrayList<>();


        for (int i = 0; i < catList.size(); i++) { 
            //finding the index of selected catagory
            if (catList.get(i) == cat)
                iList.add(i);
        }
        int min = sizeList.get(iList.get(0));

        for (int j = 1; j < iList.size(); j++) { 
            //searching for the minimum size
            if (sizeList.get(iList.get(j)) < min) {
                min = sizeList.get(iList.get(j));
            }
        }
        return min; //returning the minimum size 
    }
}

Blog

Troop selection algorithm

Sheikh Abdur Rohit

This question was asked at TCS Code Vita round 2 which found it really interesting.

Join Our Newsletter. No Spam, Only the good stuff.

Related