У вас есть несколько камней с известными весами w1, ..., wn. Напишите программу, которая перестроит камни в две свайки, чтобы разница в весе между сваями была минимальной.Должен ли я сформировать все перестановки и комбинации для следующего?
Несмотря на то, что это одномерная проблема knastpsack, вот еще один математический способ сделать это.
Algorithm: 1D Optimization
Input: weights (sequenc of weights)
Output: left and right, two sequences with difference between sum of elements minimized
***************************************************************************************
1) Sort weights in descending order
2) initialize leftsum = 0, rightsum = 0
3) initialize leftseq = [], rightseq = []
4) for each weight in weights repeat
\t 4.1) if leftsum = 0 then
\t \t 4.1.1) leftsum = weight
\t \t 4.1.2) leftseq.add(weight)
\t 4.2) else if rightsum = 0 then
\t \t 4.2.1) rightsum = weight
\t \t 4.2.2) rightseq.add(weight)
\t 4.3) else
\t \t 4.3.1) error_left = absolute(leftsum - weight)
\t \t error_right = absolute(rightsum - weight)
\t \t 4.3.2) if error_left >= error_right then
\t \t \t 4.3.2.1) rightsum = rightsum + weight
\t \t \t 4.3.2.2) rightseq.add(weight)
\t \t 4.3.3) else
\t \t \t 4.3.3.1) leftsum = leftsum + weight
\t \t \t 4.3.3.2) leftseq.add(weight)
// And here is a sample implementation of the above hypothesis in python
numbers = [1, 23, 100, 857, 890, 78, 54, 789, 34, 47, 900];
#numbers = [1, 23, 16, 5, 2]
print numbers
numbers.sort(reverse=True)
print numbers
leftSum = 0;
rightSum = 0;
leftSeq = [];
rightSeq = [];
for num in numbers:
\t if leftSum == 0:
\t \t leftSum = num;
\t \t leftSeq.append(num);
\t elif rightSum == 0:
\t \t rightSum = num;
\t \t rightSeq.append(num);
\t else:
\t \t errorLeft = abs(leftSum - num);
\t \t errorRight = abs(rightSum - num);
\t \t if errorLeft >= errorRight:
\t \t \t rightSum += num;
\t \t \t rightSeq.append(num);
\t \t else:
\t \t \t leftSum += num;
\t \t \t leftSeq.append(num);
print leftSum;
print rightSum;
print leftSeq;
print rightSeq;
\t \tОн должен работать. Ваши последовательности теперь находятся в leftseq и rightseq.
Нет. Вам не нужно создавать все комбинации 2^n. Есть два способа избежать этого.
Даже если вы найдете алгоритм, помните, что вы ДОЛЖНЫ узнать, как создать свой собственный алгоритм сортировки с предварительной фильтрацией. Ибо в реальной жизни есть много задач, в которых вам понадобится этот навык.
Это прекрасное назначение. Что вы пытались решить? Как это работает? Какие проблемы (если есть) у вас есть с вашим решением? –
Я еще ничего не сделал, просто думая об этой проблеме как о знании. Мне нужно попробовать все возможные комбинации? (Новичок в этом мире: p) –
Чтобы ответить на вопрос в своем заголовке напрямую, нет, вам не нужно формировать каждую комбинацию. – HavelTheGreat