# алгоритм – The success of the Bond missions

## Question:

Found one interesting problem. I will think about a solution and it would be nice to hear your suggestions:

Every month, James Bond receives a list of missions. Based on his rich experience, he calculates the probability of successfully completing the missions of each of his Jimi Bond number X cousins.

Your program must process this data and find the division of missions between cousins ​​to give you the highest probability that all missions will be completed successfully.

Note: The probability that all missions will be successful is equal to the product of the probabilities that individual missions will be successful.

Input format

The first line contains an integer N – the number of missions (1 <= N <= 20). The next N lines contain N integers each from 0 to 100, inclusive. The j-th integer on the i-th line is the probability that cousin i will successfully complete mission j. The probability is given as a percentage.

Output Format

Print the maximum probability of successful completion of all missions, in percent.

A conclusion that differs from the official answer by no more than +0.000001 will be accepted.

Examples

` `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``

Explanation for the 3rd example:

If Jimmy 1 assigns the 3rd mission, Jimmy 2 assigns the 1st mission, and Jimmy 3 assigns the 2nd mission, then we get a success rate of 1.0 * 0.13 * 0.7 = 0.091 = 9.1%. All other mission distribution options give a lower probability of success.

PS A question for the administration: I often solve problems of this type (sports programming) and if I offer them for solving (also often) on this forum, will you think that I flooded your site, and will it follow this ban?

Like I figured it out. I'll test it tonight and report the results.

Solution:

DP on bit masks. We will store in the array f the answers of a smaller dimension to our problem. Indices f – distribution of missions for cousins.

Consider f[i] . Let's look at the binary representation of the number i . For example i = 100110.

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

This means that f[i] contains the answer, and if a task was given to a cousin with number k , then the k -th bit is equal to 1. Moreover, if the number of non-zero bits in number i is 3, then we distributed cousins ​​for the first 3 missions.

More specific implementation:

Iterate over all the masks (from 0 to 2^20 – 1 ~ 10^6) representing our distribution (1). For each mask, we count the number of units in it – this is the number of distributed missions m (2). We look: which cousins ​​do not perform any tasks with us (3). We try to assign a task v+1 to some cousin. (4) all

a[i, j] – probability of completion of mission j by cousin 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;
``````

we get the answer when all the cousins ​​are distributed, i.e. all bits = 1 (f[2^n-1]).

So the solution runs in N*2^N ~ 20.000.000 (< 1 second the algorithm will run).

Full code:

``````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

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

pow := 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.
``````
Scroll to Top