variation of bin packing problem




Comment hidden because of low score. Click to expand.
0
of 0 vote

You can get all possible subsets of the input set.
The sum each value in each subset.
Add the subset to a Map<Integer,List<Set>>, where the key is the sum and the List contains the subset.
You can then iterate through the Map's values which is a List of Sets.
If the List of Sets size (e.g. List<Set>.size()) if equal to the 'bin' size and the List contains each element of the original Set then you have an answer.

private static String binary(int numOfBits, int value) {
		StringBuilder builder = new StringBuilder();
		while (numOfBits>0) {
			int a = value % 2;
			if (a>0) builder.append("1");
			else builder.append("0");
			value /= 2;
			numOfBits--;
		}
		return builder.toString();
	}

	private static List<Set<Integer>> subsets(int[] array) {
		List<Set<Integer>> result = new LinkedList<Set<Integer>>();
		int size = array.length;
		int max = (int) ((Math.pow(2, size)) - 1);
		List<String> binaryValues = new LinkedList<String>();
		for (int i = 1; i<=max; i++) {
			String binary = binary(size, i);
			binaryValues.add(binary);
		}
		for (String s : binaryValues) {
			Set<Integer> set = new HashSet<Integer>();
			for (int i=0; i<s.length(); i++) {
				if (s.charAt(i)=='1')
					set.add(array[i]);
			}
			result.add(set);
		}
		return result;
	}

	private static int sum(Set<Integer> set) {
		int result = 0;
		for (int i : set) {
			result += i;
		}
		return result;
	}

	private static int totalOfElements(List<Set<Integer>> list) {
		int result = 0;
		for (Set<Integer> s : list) {
			result += s.size();
		}
		return result;
	}

	private static List<List<Set<Integer>>> solve(int[] items, int bins) {
		List<Set<Integer>> subsets = subsets(items);
		Map<Integer,List<Set<Integer>>> hash = new HashMap<Integer,List<Set<Integer>>>();
		for (Set<Integer> s : subsets) {
			int sum = sum(s);
			List<Set<Integer>> l = hash.get(sum);
			if (l==null)
				l = new LinkedList<Set<Integer>>();
			l.add(s);
			hash.put(sum, l);
		}
		List<List<Set<Integer>>> list = new LinkedList<List<Set<Integer>>>();
		for (List<Set<Integer>> l : hash.values()) {
			if (l.size()==bins && totalOfElements(l)==items.length)
				list.add(l);
		}
		return list;
	}

- phishman3579 February 15, 2015 | Flag Reply




Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More