java - 在容量为 M 的 K 个房间中分配 N 吨食物

Question

我在网上发现了这个问题:

You have N tonnes of food and K rooms to store them into. Every room has a capacity of M. In how many ways can you distribute the food in the rooms, so that every room has at least 1 ton of food.

我的方法是递归地找到满足问题条件的所有可能变体。我从一个大小为 K 的数组开始，初始化为 1。然后我不断地为数组的每个元素加 1，并递归地检查新数组是否满足条件。然而，递归树变得太大太快，对于稍高的 N、K 和 M 值，程序花费的时间太长。

完成此任务的更有效算法是什么？现有算法实现是否有优化？

这是我的实现:

import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;

public class Main {
    // keeping track of valid variations, disregarding duplicates
    public static HashSet<String> solutions = new HashSet<>();

    // calculating sum of each variation
    public static int sum(int[] array) {
        int sum = 0;
        for (int i : array) {
            sum += i;
        }

        return sum;
    }

    public static void distributionsRecursive(int food, int rooms, int roomCapacity, int[] variation, int sum) {
        // if all food has been allocated
        if (sum == food) {
            // add solution to solutions
            solutions.add(Arrays.toString(variation));
            return;
        }

        // keep adding 1 to every index in current variation
        for (int i = 0; i < rooms; i++) {
            // create new array for every recursive call
            int[] tempVariation = Arrays.copyOf(variation, variation.length);
            // if element is equal to room capacity, can't add any more in it
            if (tempVariation[i] == roomCapacity) {
                continue;
            } else {
                tempVariation[i]++;
                sum = sum(tempVariation);
                // recursively call function on new variation
                distributionsRecursive(food, rooms, roomCapacity, tempVariation, sum);
            }
        }
        return;
    }

    public static int possibleDistributions(int food, int rooms, int roomCapacity) {
        int[] variation = new int[rooms];
        // start from all 1, keep going till all food is allocated
        Arrays.fill(variation, 1);
        distributionsRecursive(food, rooms, roomCapacity, variation, rooms);
        return solutions.size();
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int food = in.nextInt();
        int rooms = in.nextInt();
        int roomCapacity = in.nextInt();

        int total = possibleDistributions(food, rooms, roomCapacity);
        System.out.println(total);
        in.close();
    }
}

Answer 1

是的，如果您以幼稚的方式执行此操作，您的递归树将会变大。假设您有 10 吨重物和 3 个房间，并且 M=2。一种有效的排列是 [2,3,5]。但是您还有 [2,5,3]、[3,2,5]、[3,5,2]、[5,2,3] 和 [5,3,2]。所以对于每个有效的数字分组，实际上有 K!排列。

解决这个问题的一个可能更好的方法是确定有多少种方法可以使 K 个数字(最小 M 和最大 N)加起来等于 N。首先让第一个数字尽可能大，这将是 N-(M*(K-1))。在我的示例中，这将是:

10 - 2*(3-1) = 6

给出答案[6,2,2]。

然后，您可以构建一个算法来调整数字，通过从左向右“移动”值来得出有效组合。在我的示例中，您将拥有:

6,2,2
5,3,2
4,4,2
4,3,3

您可以通过确保值从左到右递减来避免看似无限的递归。例如，在上面你永远不会有 [3,4,3]。

如果您真的想要所有 有效排列，您可以为上述每个组合生成排列。不过，我怀疑这不是必需的。

我认为这应该足以让您开始寻找一个好的解决方案。