java - Java 搜索算法 - 电梯递归函数 - 与基本情况的斗争

Question

电梯的容量通常受到限制，无论是空间(人)还是负载(公斤)。想象一下我们有小型电梯，最多可运载 6 人，最大载重量500公斤。假设有 13 个人正在等待，其体重如下:10, 30, 40, 41, 80, 90, 50, 55,92、66、82、62 和 70 公斤。编写一个递归程序，找到一组不存在的人超过最大容量，但具有最大可能负载(以千克为单位)。 (提示:有一个有效的超过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);

}}

我的问题是理解和使用基本案例:

• 当人数未超过最大限制时。你有一个解决方案。
• 但是我该如何实现这两个目标呢？

Answer 1

这是一个有点困惑的解决方案*，我将其与 here 的信用放在一起。 , here和 here .

基本上，对于每次迭代，将组合及其总和添加到 HashMap。

然后按值对 HashMap 进行排序。

最后，循环遍历 HashMap 并找到最接近目标的值。

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;
}

这是一个online例如，int arr[] = {1,2,3,4,5,6,7,8};，排列设置为 3，目标设置为 14。

_{*这只是复制/粘贴并进行一两个小修改，但更多的是如何获得解决方案的想法}