Какой алгоритм использовать для определения минимального количества действий, необходимых для доведения системы до & ldquo; Zero & rdquo; государство?
class StringHelper
{
static void Main(string[] args)
{
string str = "Hi my name is vikas bansal and my email id is bansal.vks@gmail.com";
int offSet = 10;
List<string> chunks = chunkMyStr(str, offSet);
Console.Read();
}
static List<string> chunkMyStr(string str, int offSet)
{
List<string> resultChunks = new List<string>();
for (int i = 0; i < str.Length; i += offSet)
{
string temp = str.Substring(i, (str.Length - i) > offSet ? offSet : (str.Length - i));
Console.WriteLine(temp);
resultChunks.Add(temp);
}
return resultChunks;
}
}
7 ответов
На самом деле это похоже на работу, в которой может помочь концепция двойной записи.
Ваши транзакции могут быть структурированы в бухгалтерских записях так:
Alice Bill Charles Balance
Alice -> Bill $10 10 10- 0 0
Bill -> Alice $1 9 9- 0 0
Bill -> Charles $5 9 4- 5- 0
Charles -> Alice $5 4 4- 0 0
И вот оно. При каждой транзакции вы кредитует один счет главной книги и дебетует другой, так что баланс всегда равен нулю. В конце вы просто определяете минимальное количество транзакций, которое будет применено к каждой учетной записи, чтобы вернуть ее к нулю.
В этом простом случае это простой перевод 4 долларов от Билла к Алисе. Что вам нужно сделать, так это уменьшить хотя бы одну учетную запись (но лучше две) до нуля для каждой добавленной транзакции. Допустим, у вас есть более сложный:
Alice Bill Charles Balance
Alice -> Bill $10 10 10- 0 0
Bill -> Alice $1 9 9- 0 0
Bill -> Charles $5 9 4- 5- 0
Charles -> Alice $5 4 4- 0 0
Charles -> Bill $1 4 5- 1 0
Тогда необходимые транзакции будут такими:
Bill -> Alice $4 0 1- 1 0
Bill -> Charles $1 0 0 0 0
К сожалению, есть некоторые состояния, в которых эта простая жадная стратегия не дает наилучшего решения (слава j_random_hacker за указание это из). Один пример:
Alan Bill Chas Doug Edie Fred Bal
Bill->Alan $5 5- 5 0 0 0 0 0
Bill->Chas $20 5- 25 20- 0 0 0 0
Doug->Edie $2 5- 25 20- 2 2- 0 0
Doug->Fred $1 5- 25 20- 3 2- 1- 0
Очевидно, это можно было бы изменить за четыре хода (так как четыре хода - это все, что нужно, чтобы добраться туда), но, если вы выберете свой первый ход неразумно (Эди-> Билл $ 2) , пять - это минимум, который вам сойдет с рук.
Вы можете решить эту конкретную проблему с помощью следующих правил:
- (1) если вы можете стереть два остатка, сделайте это.
- (2) в противном случае, если вы можете стереть один уравновесить и настроить себя на уничтожение двоих в следующем ходу, сделайте это.
- (3) в противном случае уничтожьте любой баланс.
Это приведет к следующей последовательности:
- (a) [1 ] не применимо, [2] может быть достигнуто с помощью
Alan-> Bill $ 5. - (b) [1] может быть выполнено с помощью
Chas-> Bill $ 20. - ] (c) и (d), аналогичные рассуждения с Дугом, Эди и Фредом для четырех ходов
Однако это работает просто из-за небольшого количества возможностей. По мере увеличения числа людей и усложнения групповых взаимоотношений вы ' Скорее всего, мне понадобится исчерпывающий поиск, чтобы найти минимальное количество необходимых ходов (в основном правила 1, 2 и 3 выше, но расширенные для обработки большей глубины).
Я думаю, что это то, что потребуется, чтобы дать вам наименьшее число сделок при любых обстоятельствах. Однако может случиться так, что это не требуется для наилучшего ответа (в данном случае лучшего, означающего максимальную «отдачу на доллар»). Может быть, даже базовый набор правил 1/2/3 даст вам достаточно хороший ответ для ваших целей.
Интуитивно это звучит как NP-полная проблема (сводится к проблеме, очень похожей на упаковку контейнеров), однако следующий алгоритм (модифицированная форма упаковки контейнеров) должен быть довольно хорошим (нет время для доказательства, извините).
Вычтите позиции всех, то есть из вашего примера выше:
Алиса = 4 доллара Счет = -4 $ Charles = 0 долл. США
Отсортируйте всех чистых кредиторов от самого высокого до самого низкого и всех должников от самого низкого до самого высокого, затем сопоставьте, перебирая списки.
В какой-то момент вам может потребоваться разделить долги человека, чтобы вычистить все - здесь, вероятно, лучше всего разделить на самые большие возможные куски (т. Е. Сначала на корзины с наибольшим оставшимся пространством).
Это займет что-то вроде O (n log n) (опять же, требуется надлежащее доказательство).
См. Проблема с разделением и Bin Packing для получения дополнительной информации (первое - очень похожая проблема, и если вы ограничиваетесь транзакциями с фиксированной точностью, то это эквивалентно - конечно, требуется доказательство).
Итак, первый шаг - полностью игнорировать транзакции , Просто сложите их. Все, что вам действительно нужно знать, - это чистая сумма долга, которую человек должен / владеет.
Вы можете очень легко найти транзакции, создав сумасшедший граф потока и определив максимальный поток. Затем минус ...
Некоторые частичные уточнения: Есть исходный узел, приемный узел и узел для каждого человека. Между каждой парой узлов будет граница, за исключением отсутствия границы между исходным узлом и приемным узлом. Границы между людьми имеют бесконечную вместимость в обоих направлениях. Ребра, идущие от узла источника к человеку, имеют емкость, равную чистому долгу человека (0, если у них нет чистого долга). Ребра, идущие от узла-человека к узлу-приемнику, имеют емкость, равную чистой сумме денег, которую человек должен (0, если у них нет чистой задолженности).
Применение максимального потока и / или минимального отсечения даст вам набор переводов. Фактическая сумма потока будет соответствовать тому, сколько денег будет переведено.
Только если кто-то должен более 2 человек, которые также должны одному и тому же набору, вы можете уменьшить количество транзакций из простого набора.
То есть простой набор - это просто найти каждый баланс и погасить его. Это не более N! транзакции.
Если A должен B и C, и некоторое подмножество BC должно друг другу, значит, B должен C, то вместо: A -> B, A -> C (3 транзакции). Вы должны использовать: A -> B, B -> C (2 транзакции).
Другими словами, вы строите ориентированный граф и хотите обрезать вершины, чтобы максимизировать длину пути и минимизировать общее количество ребер.
Извините, у меня нет для вас алгоритма.
Вы сможете решить эту проблему за O (n), сначала определив, сколько каждый человек должен и должен. Перенести долги любого, кто имеет меньшую задолженность, чем он должен, своим должникам (таким образом, превратив этого человека в конечную точку). Повторяйте, пока вы не сможете больше переводить долги.
Если вы возьмете состояния как узлов графа , то вы сможете использовать алгоритм кратчайшего пути, чтобы узнать ответ.
Я нашел практическое решение, которое реализовал в Excel:
выяснить, у кого больше всего
, пусть этот человек выплатит полную сумму своему долгу тому, кто должен получить больше всего
, который заставляет первого человека ноль
повторять этот процесс с учетом того, что у одного из (n-1) человек изменилась сумма
Это должно привести к максимуму (n-1) переводов и хорошему Дело в том, что никто не делает более одного платежа. Возьмите (измененный) пример jrandomhacker:
a = -5 b = 25 c = -20 d = 3 e = -2 f = -1 (сумма должна быть равна нулю!)
c -> b 20. результат: a = -5 b = 5 c = 0 d = 3 e = -2 f = -1
a -> b 5 результат: a = 0 b = 0 c = 0 d = 3 e = -2 f = -1
e -> d 2 результат a = 0 b = 0 c = 0 d = 1 e = 0 f = -1
f -> d 1
Теперь все довольны, и никого не беспокоят два или более платежей. Как видите, возможно, что один человек получит более одного платежа (человек d в этом примере).