Как найти наименьшие числа в квадратной таблице, только по одному столбцу и по одному на строку [дубликат]

Строка ошибки «Ссылка на объект, не установленная на экземпляр объекта.» указывает, что вы не назначили экземпляр объекта объектной ссылке, и все же вы получаете доступ к свойствам / методам этого объекта.

например: скажем, у вас есть класс под названием myClass и он содержит одно свойство prop1.

public Class myClass
{
   public int prop1 {get;set;}
}

Теперь вы получаете доступ к этому prop1 в каком-то другом классе, как показано ниже:

public class Demo
{
     public void testMethod()
     {
        myClass ref = null;
        ref.prop1 = 1;  //This line throws error
     }
}

выше строки выдает ошибку, потому что ссылка класса myClass объявлена, но не создана, или экземпляр объекта не назначается referecne этого класса.

Чтобы исправить это, вам нужно создать экземпляр (присвоить объект ссылке на этот класс).

public class Demo
{
     public void testMethod()
     {
        myClass ref = null;
        ref = new myClass();
        ref.prop1 = 1;  
     }
}
9
задан Matt 2 August 2011 в 22:18
поделиться

2 ответа

Это проблема двухстороннего сопоставления с максимальной стоимостью. Классический способ его решения - использовать венгерский алгоритм .

В принципе, у вас есть двудольный граф: левый набор - это строки, а правый набор - это столбцы. Каждое ребро из строки i в столбец j имеет стоимость matrix[i, j]. Найдите соответствие, которое максимизирует затраты.

9
ответ дан IVlad 24 August 2018 в 04:53
поделиться

Для начала вы можете использовать динамическое программирование.

В вашем прямом подходе вы делаете точно такие же вычисления много раз.

Например, в какой-то момент вы ответьте на вопрос: «Для последних трех столбцов с уже занятыми строками 1 и 2, как я могу максимизировать сумму?» Вы дважды вычисляете ответ на этот вопрос, один раз, когда вы выбираете строку 1 из столбца 1 и строки 2 из столбца 2 и один раз, когда вы выбираете их наоборот.

Так что не делайте этого. Cache ответ, а также кешировать все похожие ответы на все подобные вопросы - и повторно использовать их.

У меня нет времени прямо сейчас, чтобы проанализировать время работы этот подход. Я думаю, что это O (2 ^ n) или около того. Позже может быть ...

0
ответ дан Nemo 24 August 2018 в 04:53
поделиться
Другие вопросы по тегам:

Похожие вопросы: