fork(6) download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. /* Name of the class has to be "Main" only if the class is public. */
  8. class Ideone
  9. {
  10.   public static void main(String[] args)
  11.   {
  12.     Set<Integer> unv = new HashSet<>();
  13.     unv.add(1);
  14.     unv.add(2);
  15.     unv.add(3);
  16.     unv.add(4);
  17.     unv.add(5);
  18.     Set<Integer> s1 = new HashSet<>();
  19.     s1.add(4);
  20.     s1.add(1);
  21.     s1.add(3);
  22.     Set<Integer> s2 = new HashSet<>();
  23.     s2.add(2);
  24.     s2.add(5);
  25.     Set<Integer> s3 = new HashSet<>();
  26.     s3.add(1);
  27.     s3.add(4);
  28.     s3.add(3);
  29.     s3.add(2);
  30.     Set sets[] =
  31.     {
  32.       s1, s2, s3
  33.     };
  34.     Map<Set, Integer> costs = new HashMap<>();
  35.     costs.put(s1, 5);
  36.     costs.put(s2, 10);
  37.     costs.put(s3, 30);
  38.     System.out.println(minCostCollection(unv, sets, costs, new ArrayList<Set>(), sets.length - 1));
  39.   }
  40.  
  41.   public static int minCostCollection(Set<Integer> unv, Set<Integer>[] sets, Map<Set, Integer> costs, List<Set> list,
  42.                                       int pos)
  43.   {
  44.  
  45.     if (unv.size() == 0)
  46.     {
  47.       int cost = 0;
  48.       for (Set s: list)
  49.       {
  50.         cost = cost + costs.get(s);
  51.       }
  52.       return cost;
  53.     }
  54.     if (pos < 0)
  55.       return Integer.MAX_VALUE;
  56.     Set<Integer> unvCopy = new HashSet<>(unv);
  57.     List<Set> list1 = new ArrayList<>(list);
  58.     list.add(sets[pos]);
  59.     for (Integer elem: sets[pos])
  60.     {
  61.       unv.remove(elem);
  62.     }
  63.     int cost1 = minCostCollection(unv, sets, costs, list, pos - 1);
  64.     int cost2 = minCostCollection(unvCopy, sets, costs, list1, pos - 1);
  65.     return Math.min(cost1, cost2);
  66.   }
  67. }
Success #stdin #stdout 0.1s 320320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
15
https://ideone.com/hUY3Am
language:
Java (HotSpot 12)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!