Максимальная сумма из уникальных цифр

Question

Здесь я нахожу максимальную сумму, которая может быть образована этими (вводимыми пользователем) числами, но числа, которые используются для суммирования, не должны иметь общих цифр.

• Нам даны n номера.
• Мы смотрим на все подмножества этих чисел, где каждая цифра встречается не более одного раза.
• Для этого подмножества мы вычисляем суммы.
• Затем ищем максимум этой суммы.

например. вводим числа случаев n = 5

0  1   2  3 - > 6  ( no repeated digits here ) 0+1+2+3
3  30  8  1 - > 39 ( here 3  is repeated so choose max from 3 & 30 i.e. 30) 30+8+1
11 21 31 41 - > 41 ( here 1 is repeated to all so max number will print ) 41
11 5  45 88 - > 99 ( here 5 is repeated so choose max from 45 & 5 i.e 45 ) 11+88+45
17 69 78 89 -> 147  (69 + 78) = 147 


int sum(int Ticket[], int n)
{
    int max;
    int abc;
    for (int i = 0; i <= n; i++) {
        for (int k = 0; k <= n; k++) {
            abc = Ticket[i];
            max = Ticket[i] + Ticket[i]
                int len = to_string(abc).length();

            for (int j = 0; j <= len; j++) {
                std::string nstr = std::to_string(abc);
                std::cout << "->" << nstr[j];
            }
        }
    }
return max;
}
int main()
{ 
       // n total number of array or numbers
        int max = sum(Ticket, n);
}

Вопрос в том, как проверить уникальные цифры каждого числа и сформировать максимальную сумму.

Answer 1

Размер набора всех подмножеств цифр равен 2 ^ 10.

Учитывая номер, вы можете хранить table[digits used]=value.

Учитывая таблицу с некоторыми записями и номером, вы можете для каждой записи определить, можете ли вы использовать этот номер. Если это так, вы добавляете table[old digit and digits from number]=new sum, если там еще нет записи с более высоким значением. При этом учитывайте тот факт, что table[no digits]=0.

Это займет O (2 ^ n) времени для ввода O (n), так как записи таблицы растут экспоненциально, но не более, чем O (n * 1024), поскольку экспоненциальный рост записей не может превышать заполнение всей таблицы. .

Наивно, таблица может быть реализована как std::unordered_map< unsigned char, unsigned int > с использованием битовых масок.

Это решение для динамического программирования.