UC知道pascal编程题:bond
来源：百度知道 编辑：UC知道 时间：2024/05/17 06:29:24
所有人知道秘密特务007，詹姆斯·邦德，但是很少人知道，许多时候他并不亲自去做任务，而是让他的表兄弟们完成。现在每当詹姆斯收到任务，他就将任务分发给大家，于是他需要你的帮助。
詹姆斯每月收到一张任务单。对于每一个任务，他都根据以往的经验，计算出他和其他几位兄大。
注弟完成的成功概率。你的程序应当找到一种分配方案，使得所有任务都被成功完成的概率最：所有任务都被成功完成的概率，等于每个任务都被成功完成的概率之积。
【输入格式】
第一行包含一个整数N(<=20)，表示有N个任务，而他有N个兄弟来替他完成。
接下来包含N行，每行包含N个0到100之间的整数。第i行第j列的数，表示第i个任务被第j个兄弟完成的成功概率。概率以百分比的形式给出。
【输出格式】
仅一行，输出所有任务都被成功完成的最大概率，要求误差不超过±10-6。
【测试样例】
bond.in
2
100 100
50 50
bond.out
50.000000
bond.in
2
0 50
50 0
bond.out
25.00000
bond.in
3
25 60 100
13 0 50
12 70 90
bond.out
9.10000
求解答，分析最好，有程序代码也行，最好是pascal的,c的也行
分析：
此题一眼扫过去，基本没什么数学方法，只有用搜索方法。因不满足动态搜索的条件，只可用普通搜索。但若简单的列举全部情况，则最高有20！种，时间上不允许，于是只有疯狂的剪枝除叶。具体思想见程序及说明。
program bond;
type t= record
gai:shortint;{概率}
bro:shortint;{是哪个兄弟完成}
end;
var work:array [1..20,1..20] of t;{一个是哪个工作,一个是概率大小顺序,哪个兄弟完成已有bro储存}
N:shortint;max:longint;{最后结果}
yiyou:set of 1..20;{已分配工作的兄弟}
procedure init;
var ii,li,mi:shortint;
ling:t;
begin
assign(input,'bond.in');
assign(output,'bond.out');
reset(input);
rewrite(output);
readln(n);max:=0;
for ii:=1 to n do
for li:=1 to n do
begin
read(work[ii,li].gai);
work[ii,li].bro:=li;
end;{读入每一个概率与相应的兄弟和工作}
for ii:=1 to n do
for li:=1 to n-1 do
for mi:=li+1 to n do
if work[ii,li].gai<work[ii,mi].gai then
begin
ling:=work[ii,li];
work[ii