Разделение списка значений на три равных промежуточных итога
У меня есть список чисел, которые в общей сложности 540000. Я хотел бы отсортировать этот список на 3 списка, каждый из которых составляет 180000. Каков наиболее эффективный метод программирования, чтобы сделать это, предполагая, что список чисел представляет собой плоский файл с числом в линия?
5 ответов
Звучит как вариант проблемы с рюкзаком. Было бы полезно узнать размер этих чисел и посчитать - есть ли огромные различия в размере или все они похожи по масштабу - их много (>1000) или всего несколько (<100)?
Один быстрый и грязный метод состоит в том, чтобы отсортировать их в порядке размера - от наибольшего к наименьшему - затем зациклить их, поместив первое в первый список, второе во второй список, третье в третий список, а затем вернуться назад и поместите четвертый в первый список... и так далее. Может работать довольно хорошо для большого числа небольших чисел... но для разных типов наборов данных существуют другие подходы.
Как уже заметил Ян-Витц, это, вероятно, проблема типа NP-complete: это означает, что нет действительно хорошего решения для общего случая, если не использовать все возможности. Алгоритмы, которые делают это, имеют тенденцию становиться невероятно медленными по мере увеличения объема данных, с которыми они имеют дело.
Тем не менее, вот мой алгоритм для формирования подсписков, имеющих указанную сумму из заданного списка целых чисел:
Set up a place to hold your results. The results will all be lists of numbers, each some sub-set of your original list. We don't know how many such lists will result; possibly none.
Put your list of numbers into an array so you can refer to them and access them by index. In the following, I'm assuming array indices starting at 1. Say you have 10 numbers, so you put them into a 10 element array, indexed by positions 1 through 10.
For performance reasons, it may help to sort your array in descending order. It's not necessary though.
Run a first index, call it i, through this array, i.e. through index values 1 through 10.
For each index value:
select the number at index position i, call it n1.
set up a new list of numbers, where we will be assembling a sub-list. call it sublist.
add n1 to the (so far empty) sublist.
If i is already at 10, there's nothing more we can do. Otherwise,
Run a second index, call it j, through the arrray, starting at i+1 and going up to 10.
For each value of j:
select the number at index position j, call it n2.
add n2 to the sublist containing n1
calculate the sum of our sublist so far: Does it add up to 18000?
If the exact total is reached, add the current sublist to our result list.
If the total is exceeded, there's nothing we can add to make it better, so skip to the next value of j.
If the total is less than 18000, you need to pick a third number.
Run a third index, call it k, through the array, starting at j+1 and going up to 10. Skip this if j is already at 10 and there's no place to go.
For each value of k:
select the number at k, call it n3
add n3 to the sublist
check the sublist total against the expected total
if the exact total is reached, store the sublist as a result;
if it's less than the expected, start a 4th loop, and so on.
When you're done with checking a value for a loop, e.g. n4, you need to take your latest n4, n3 or whatever back out of the sublist because you'll be trying a different number next.
Whenever you find a combination of numbers with the correct sum, store it in your results set.
When you've run all your loop counters into the wall (i.e. i is 10 and there's nowhere left to go), your "results" set will contain all sub-lists of the original list that added up to the desired total. It's possible there will be none, in that case there's no (exact) solution to your problem.
If you have 3 or more sub-lists in your results set, you can check if you can find a pair of them that use non-overlapping sets of numbers from the original list. If you have 2, then there should also be a 3rd sub-list containing exactly all the numbers not contained in the first 2 lists, and you have your solution.
Мой пример кода не делает серию циклов; вместо этого он выполняет один цикл, идущий от 1 до (скажем) 10 и ищущий 18000. Затем, скажем, первое выбранное число было 2000, функция рекурсивно вызывает себя снова с подсказкой начать с 2 (= i + 1) и чтобы попытаться собрать в общей сложности 16000. Этот вызов функции затем вызывает себя снова с начальной позицией (независимо от + 1) и общим количеством (16000 - независимо от того), и он продолжает вызывать себя таким образом с подмножествами оригинала. проблема, пока нет больше места для индексов, чтобы подняться. Если он находит "хороший" подсписок в пути, он сохраняет его в наборе результатов.
Как эффективно это реализовать, зависит от того, на каком языке вы это делаете. В FORTRAN 77 нет рекурсии, Lua не реализует списки и не устанавливает эффективно, у Lisp могут возникнуть проблемы с эффективной индексацией в списке. В Java я мог бы использовать набор битов, а не подсписок. Я ничего не знаю о P4GL, так что: для реализации вы сами!
Я написал некоторый Java-код, который сделает большую часть работы за вас.
Меньший из методов принимает список чисел и итоговую сумму, которую необходимо достичь, и возвращает набор списков чисел, которые складываются в общую сумму. Вы можете запустить его с 18000 и вашим списком чисел.
Для каждого возвращенного списка номеров необходимо создать новый список, в котором отсутствуют уже использованные номера, и запустить метод на 18000 и снова.
Если этот второй вызов вернет один или несколько списков, вы поймете, что проблема разрешима, потому что оставшиеся числа также добавят 18000.
Во всяком случае, вот код. Да, это просто рекурсивная грубая сила. Весьма вероятно, что не существует проверенного метода, позволяющего последовательно добиваться большего успеха любым другим методом. Не обвиняй меня, если это продолжается долго; Вы можете сначала попробовать это с небольшими примерами.
import java.util.*;
public class Listen {
private static Set<List<Integer>> makeFrom(int total, List<Integer> numbers) {
Set<List<Integer>> results = new HashSet<List<Integer>>();
List<Integer> soFar = new ArrayList<Integer>();
makeFrom(results, total, soFar, numbers, 0);
return results;
}
private static void makeFrom(Set<List<Integer>> results, int total, List<Integer> soFar, List<Integer> numbers, int startingAt) {
if (startingAt >= numbers.size()) return;
for (int p=startingAt; p<numbers.size(); p++) {
Integer number = numbers.get(p);
List<Integer> newSoFar = new ArrayList<Integer>(soFar);
newSoFar.add(number);
int newTotal = total - number;
if (newTotal < 0) continue;
if (newTotal == 0) {
Collections.sort(newSoFar);
results.add(newSoFar);
} else {
List<Integer> newNumbers = new ArrayList<Integer>(numbers);
newNumbers.remove(number);
makeFrom(results, newTotal, newSoFar, newNumbers, startingAt + 1);
}
}
}
public static void main(String[] args) {
List<Integer> numbers = new ArrayList<Integer>();
for (int j=1; j<11; j++) numbers.add(j);
for (List<Integer> result : makeFrom(25, numbers)) {
System.out.println(Arrays.deepToString(result.toArray(new Integer[result.size()])));
}
}
}
for i as integer = 1 to 180000
put data in array 1
next i
for i as integer = 180001 to 360000
put data in array 2
next i
for i as integer = 360001 to 540000
put data in array 3
next i
Это имеет запах NP-твердости для меня - в этом случае не существует "эффективного" способа сделать это. Хотя вы, вероятно, могли бы придумать любое количество эвристик, которые могли бы справиться с этим довольно хорошо.
Сказав, что у вас все еще будут проблемы со списками типа [179998, 180001, 180001]:)