variation of bin packing problem
public class BinProblem {
public static void main(String[] args) {
int[] weight={2,3,4,5,7};
int bin=3;
System.out.println(binWeight(weight, bin));
}
private static List<List<Integer>> binWeight(int[] weight, int bin){
int sum=0;
int iDistributedWt=0;
List<List<Integer>> finalList=new ArrayList<>();
boolean bFlag=false;
for(int i=0;i<=weight.length-1;i++){
sum=sum+weight[i];
}
if(sum%bin!=0){
System.out.println("not possible.");
System.exit(0);
}
else{
iDistributedWt=sum/bin;
for(int i=0;i<=weight.length-1;i++){
bFlag=false;
if(weight[i]==0){
continue;
}
if((weight[i]==iDistributedWt)){
List<Integer> list=new ArrayList<Integer>();
list.add(weight[i]);
finalList.add(list);
}else{
for(int j=i+1;j<=weight.length-1;j++){
if((weight[i]+weight[j])==iDistributedWt){
List<Integer> list=new ArrayList<Integer>();
list.add(weight[i]);
list.add(weight[j]);
finalList.add(list);
weight[j]=0;
bFlag=true;
break;
}
}
if(!bFlag){
System.out.println("not possible.");
System.exit(0);
}
}
}
}
return finalList;
}
}
public class BinProblem {
public static void main(String[] args) {
int[] weight={2,3,4,5,7};
int bin=3;
System.out.println(binWeight(weight, bin));
}
private static List<List<Integer>> binWeight(int[] weight, int bin){
int sum=0;
int iDistributedWt=0;
List<List<Integer>> finalList=new ArrayList<>();
boolean bFlag=false;
for(int i=0;i<=weight.length-1;i++){
sum=sum+weight[i];
}
if(sum%bin!=0){
System.out.println("not possible.");
System.exit(0);
}
else{
iDistributedWt=sum/bin;
for(int i=0;i<=weight.length-1;i++){
bFlag=false;
if(weight[i]==0){
continue;
}
if((weight[i]==iDistributedWt)){
List<Integer> list=new ArrayList<Integer>();
list.add(weight[i]);
finalList.add(list);
}else{
for(int j=i+1;j<=weight.length-1;j++){
if((weight[i]+weight[j])==iDistributedWt){
List<Integer> list=new ArrayList<Integer>();
list.add(weight[i]);
list.add(weight[j]);
finalList.add(list);
weight[j]=0;
bFlag=true;
break;
}
}
if(!bFlag){
System.out.println("not possible.");
System.exit(0);
}
}
}
}
return finalList;
}
}
Get all subsets of the input set.
Create a Map<Integer,Set<List>>, where the all Lists in the Set have the same sum (which is the key in the map).
Then iterate through each value of the Map,
If the length of the Set is equal to bin size and each element of the input set is contained in the Set of Lists 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<List<Integer>> subsets(int[] array) {
List<List<Integer>> result = new LinkedList<List<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) {
List<Integer> list = new LinkedList<Integer>();
for (int i=0; i<s.length(); i++) {
if (s.charAt(i)=='1')
list.add(array[i]);
}
result.add(list);
}
return result;
}
private static int sum(List<Integer> list) {
int result = 0;
for (int i : list) {
result += i;
}
return result;
}
private static int totalOfElements(Set<List<Integer>> list) {
int result = 0;
for (List<Integer> l : list) {
result += l.size();
}
return result;
}
private static List<Set<List<Integer>>> solve(int[] items, int bins) {
List<List<Integer>> subsets = subsets(items);
Map<Integer,Set<List<Integer>>> hash = new HashMap<Integer,Set<List<Integer>>>();
for (List<Integer> l : subsets) {
int sum = sum(l);
Set<List<Integer>> s = hash.get(sum);
if (s==null)
s = new HashSet<List<Integer>>();
s.add(l);
hash.put(sum, s);
}
List<Set<List<Integer>>> list = new LinkedList<Set<List<Integer>>>();
for (Set<List<Integer>> l : hash.values()) {
if (l.size()==bins && totalOfElements(l)==items.length)
list.add(l);
}
return list;
}
public class BinProblem {
- abhishek December 16, 2014public static void main(String[] args) {
int[] weight={2,3,4,5,7};
int bin=3;
System.out.println(binWeight(weight, bin));
}
private static List<List<Integer>> binWeight(int[] weight, int bin){
int sum=0;
int iDistributedWt=0;
List<List<Integer>> finalList=new ArrayList<>();
boolean bFlag=false;
for(int i=0;i<=weight.length-1;i++){
sum=sum+weight[i];
}
if(sum%bin!=0){
System.out.println("not possible.");
System.exit(0);
}
else{
iDistributedWt=sum/bin;
for(int i=0;i<=weight.length-1;i++){
bFlag=false;
if(weight[i]==0){
continue;
}
if((weight[i]==iDistributedWt)){
List<Integer> list=new ArrayList<Integer>();
list.add(weight[i]);
finalList.add(list);
}else{
for(int j=i+1;j<=weight.length-1;j++){
if((weight[i]+weight[j])==iDistributedWt){
List<Integer> list=new ArrayList<Integer>();
list.add(weight[i]);
list.add(weight[j]);
finalList.add(list);
weight[j]=0;
bFlag=true;
break;
}
}
if(!bFlag){
System.out.println("not possible.");
System.exit(0);
}
}
}
}
return finalList;
}
}