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.10000Explanation 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?
Answer:
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
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.