Успешность выполнения миссий Бонда

Question

Успешность выполнения миссий Бонда

Рейтинг: 6Ответов: 1Опубликовано: 10.05.2011

Нашёл одну интересную задачу. Буду думать над решением и неплохо бы услышать ваши предложения:

Каждый месяц Джеймс Бонд получает список миссий. Основываясь на своем богатом опыте, он вычисляет вероятность успешного выполнения миссий каждой из своих кузин Джими Бонд номер X.

Ваша программма должна обработать эти данные и найти такое разделение миссий между кузинами, чтобы получить наибольшую вероятность того, что все миссии будут успешно выполнены.

Замечение: вероятность того, что все миссии будут успешно выполнены, равна произведению вероятностей того, что отдельные миссии будут выполнены успешно.

Формат ввода

Первая строка содержит целое число N - количество миссий (1 <= N <= 20). Следующие N строк содержат по N целых чисел от 0 до 100, включительно. j-тое целое число на i-той строке означает вероятность того, что кузина i выполнит успешно миссию j. Вероятность задана в процентах.

Формат вывода

Выведите максимальную вероятность успешного выполнения всех миссий, в процентах.

Вывод отличающийся от официального ответа не более чем на +0.000001, будет принят.

Примеры
input        input       input    
2            2           3        
100 100      0 50        25 60 100
50 50        50 0        13 0 50  
                           12 70 90 

output       output      output
50.000000    25.00000    9.10000
Пояснение к 3-му примеру:

Если Джимми 1 назначить 3-ю миссию, Джимми 2 назначить 1-ую миссию, а Джимми 3 назначить 2-ую миссию, то получим вероятность успеха равную 1.0 * 0.13 * 0.7 = 0.091 = 9.1%. Все другие варианты распределения миссий дают меньшую вероятность успеха.

P. S. Вопрос к администрации: я частенько решаю задачи такого типа (спортивное программирование) и, если я их буду предлагать для решения (тоже часто) на этом форуме, то не будете ли вы считать, что я зафлудил ваш сайт, и не последует ли за этим бан?

алгоритм

Источник: Stack Overflow на русском

Answer 1

▲ 2Принят

Вроде придумал. Сегодня вечером протестирую и сообщю результаты.

Решение:

ДП по битовым маскам. Будем хранить в массиве f ответы меньшей размерности на нашу задачу. Индексы f - распределения миссий для кузин.

Рассмотрим f[i]. Посмотрим на двоичное представление числа i. Например i = 100110.

|**№ бита**  | 5 | 4 | 3 | 2 | 1 | 0 |
|------------+---+---+---+---+---+---|
|**знач. i** | 1 | 0 | 0 | 1 | 1 | 0 |

Это значит что в f[i] находится ответ, и если дали задание кузине с номером k, то k-ый бит равен 1. Причём, если количество ненулевых битов в числе i равно 3, то мы распределили кузин для первых 3 миссий.

Конкретней реализация:

Перебираем все маски (от 0 до 2^20 - 1 ~ 10^6), представляющие наше распределение (1). Для каждой маски считаем количество единиц в ней - это количество распределённых миссий м(2). Смотрим: какие кузины у нас не выполняют никаких заданий (3). Пробуем назначить какой-нибудь кузине задание v+1. (4) всё

a[i, j] - вероятность выполнения миссии j кузиной i

    for msk := 0 to pow[n] - 1 do begin //pow[w] = 2^w; (1)
            v := q(msk); //(2)
            for i := 1 to n do // перебираем всех кузин
                    if msk and pow[i-1] = 0 then //(3)
                            f[msk or pow[i-1]] := max(f[msk or pow[i-1]],f[msk]*a[v+1,i]);// (4)
    end;

ответ получим, когда распределили всех кузин, т. е. все биты = 1 (f[2^n-1]).

Таким образом решение работает за N*2^N ~ 20.000.000 (< 1 секунды будет выполнятся алгоритм).

Полный код:

const
        maxN     = 21;
        maxS     = 1 shl maxN;   
var
        n,m,i,j,msk,v   : longint;    
        a               : array [1..maxN,1..maxN] of double;    
        f               : array [1..maxS] of double;    
        pow             : array [0..maxN] of longint;    
function q(w : longint) : longint;
        var
                res     : longint;
        begin
                res := 0;
                while w > 0 do begin
                        if w and 1 = 1 then
                                inc(res);
                        w := w shr 1;
                end;
                q := res;
        end;    
function max(w1,w2 : double) : double;
        begin
                if w1 > w2 then
                        max := w1
                else
                        max := w2;
        end;    
begin
        readln(n);

        for i := 1 to n do
                for j := 1 to n do begin
                        read(a[i,j]);
                        a[i,j] := a[i,j] / 100;
                end;

        pow[0] := 1;
        for i := 1 to maxN do
                pow[i] := pow[i-1] shl 1;

        for i := 1 to n do
                f[pow[i-1]] := a[1,i];
 
        for msk := 0 to pow[n] - 1 do begin
                v := q(msk);
                for i := 1 to n do
                        if msk and pow[i-1] = 0 then
                                f[msk or pow[i-1]] := max(f[msk or pow[i-1]],f[msk]*a[v+1,i]);
        end;

        writeln(f[pow[n]-1]*100:0:10);
end.

Успешность выполнения миссий Бонда

Ответы