Я нашел эту проблему в Интернете: < /p>
У вас есть n тонны еды и k комнат для их хранения. Каждая комната имеет способность М., сколько способов вы можете распространять еду в комнатах, так что в каждой комнате есть как минимум 1 тонна еды. Я начинаю с массива размера k, инициализированного до 1. Затем я продолжаю добавлять 1 к каждому элементу массива и повторяет, удовлетворяет ли новый массив это состояние. Тем не менее, дерево рекурсии становится слишком большим слишком быстро, и программа занимает слишком много времени для немного более высоких значений n, k и m. < /p>
Что было бы более эффективным алгоритмом для достижения этой задачи? Существуют ли какие -либо оптимизации, которые необходимо сделать с существующей реализацией алгоритма?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 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 == roomCapacity) {
continue;
} else {
tempVariation++;
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();
}
}
Подробнее здесь: https://stackoverflow.com/questions/354 ... m-capacity
