Search Algorithm Java - Elevator Recursive function - Struggle with base cases

Question

Lifts are usually limited in capacity, both in space (persons) as in load (kgs). Imagine we have a small lift which is capable of transporting a maximum of 6 persons and a maximum load of 500kg. Suppose 13 people are waiting with the following weights: 10, 30, 40, 41, 80, 90, 50, 55, 92, 66, 82, 62 and 70kg. Write a recursive program that finds a group of people that does not exceed the maximum capacities, but has the maximum possible load in kg. (Hint: there is a valid solution that exceeds 470kg)

public static void main (String[] Args)
{

     ArrayList<Integer> s = new ArrayList<Integer>(); //List of unexplored
     int[] weight0 = { 10, 30, 40, 41, 80, 90, 50, 55, 92, 66, 82, 62,70}; //Initial state
     int target = 500; //Goal state
     System.out.println(liftGroup(weight0,0,target, s) + " way(s)"); //Recursive function

}

static int liftGroup (int[] weight,int c,int target, ArrayList<Integer> s){

    assert weight != null : "array should be initialized";
    assert c >= 0 && c <= weight.length;
    assert s != null : "ArrayList should be initialized";
    int sumOfUntried = 0;

    if (c > 6) {
        showSoulution(s);
        return 1;
    }
    else if (target < 0) {
        return 0;
    }
    else if (c >= weight.length) {  //that's okay? 
        return 0;
    }

    int min = weight[c];
    for (int i = c; i < weight.length; i++) {
        sumOfUntried += weight[i];
        if(weight[i]<min)
            min=weight[i];
    }

    if(min>target) // If you find one BIG fatty 
    {
        return 0;
    }
    if (sumOfUntried > target) { //Correct
        return 0;
    }
    else {
        s.add(weight[c]);
        int with = liftGroup(weight, c + 1, target - weight[c], s);
        s.remove(s.size() - 1);
        int without = liftGroup(weight, c + 1, target, s);
        return with + without;
    }
}

/*
* Prints the ArrayList with the solution
*/
private static void showSoulution(ArrayList<Integer> s) 
{

    assert s != null : "ArrayList should be initialized";
    System.out.println("Solution: " + s);

}}

My problem is understanding and using the base case:

• When the number of persons does not exceed the maximum limits. You've got a solution.
• But how do I comply with the two goals?

Answer 1

Here's a little bit of a messy solution*, which I threw together with credit from here, here and here.

Basically, for each iteration, add the combination, and its sum to a HashMap.

Then sort the HashMap by value.

Finally, loop through HashMap and find closest value to your target.

static Map<String, Integer> myMap = new HashMap<>();

static void combinationUtil(int arr[], int data[], int start,
        int end, int index, int r) {
    int sum = 0;
    StringBuilder sb = new StringBuilder();
    if (index == r) {
        for (int j = 0; j < r; j++) {

            sb.append(data[j]).append(",");
            sum += data[j];

            System.out.print(data[j] + " ");
        }
        myMap.put(sb.toString(), sum);
        sum = 0;
        sb = new StringBuilder();
        System.out.println("");
        return;
    }
    for (int i = start; i <= end && end - i + 1 >= r - index; i++) {
        data[index] = arr[i];
        combinationUtil(arr, data, i + 1, end, index + 1, r);
    }
}

static void printCombination(int arr[], int n, int r) {
    int data[] = new int[r];
    combinationUtil(arr, data, 0, n - 1, 0, r);
}

public static void main(String[] args) {
    int arr[] = {10, 30, 40, 41, 80, 90, 50, 55, 92, 66, 82, 62, 70};
    int r = 6; //as you have 6 people
    int n = arr.length;
    printCombination(arr, n, r);
    myMap = sortByValue(myMap);
    System.out.println(searchClosest(myMap, 500)); //500 is the target
}

public static <K, V extends Comparable<? super V>> Map<K, V> sortByValue(Map<K, V> map) {
    return map.entrySet()
            .stream()
            .sorted(Map.Entry.comparingByValue(/*Collections.reverseOrder()*/))
            .collect(Collectors.toMap(
                    Map.Entry::getKey,
                    Map.Entry::getValue,
                    (e1, e2) -> e1,
                    LinkedHashMap::new
            ));
}

public static String searchClosest(Map<String, Integer> map, int value) {
    double minDistance = Double.MAX_VALUE;
    String bestString = null;

    for (Map.Entry<String, Integer> entry : map.entrySet()) {
        double distance = Math.abs(entry.getValue() - value);
        if (distance < minDistance) {
            minDistance = distance;
            bestString = entry.getKey();
        }
    }
    return bestString;
}

Here's an online example with int arr[] = {1,2,3,4,5,6,7,8}; and the permutations set to 3, and target of 14.

_{*This is just copied/pasted with one or two minor modifications but is more just an idea of how to get your solution}