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.
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.
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.
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.
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).
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 := 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.