SSL 1635——系统可靠性

本文主要是介绍SSL 1635——系统可靠性，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

　　一个系统由若干部件串联而成，只要有一个部件故障，系统就不能正常运行，为提高系统的可靠性，每一部件都装有备用件，一旦原部件故障，备用件就自动进入系统。显然备用件越多，系统可靠性越高，但费用也越大，那么在一定总费用限制下，系统的最高可靠性等于多少？
　　给定一些系统备用件的单价Ck，以及当用Mk个此备用件时部件的正常工作概率Pk（Mk），总费用上限C。求系统可能的最高可靠性。

Input

第一行：n C
第二行：C1 P1(0) P1(1) … P1(X1) （0<=X1<=[C/Ck]）
…
第n 行：Cn Pn(0) Pn(1) … Pn(Xn) （0<=Xn<=[C/Cn]）

Output

最高可靠性

Sample Input

2 20
3 0.6 0.65 0.7 0.75 0.8 0.85 0.9
5 0.7 0.75 0.8 0.8 0.9 0.95
Sample Output

0.6375

//结果保留小数点后4位．
Hint

n<=10,C<=100,1<=Ci<=20

---

设f[i,j]为取到第i个系统备用件用了j元的最大系统可靠性。
f[i,j]:=max(f[i,j],f[i-1,j-k*a[i]]*p[i,k])
0<=i<=n
0<=j<=m
0<=k<=c div a[i]
f[0,0]:=1

---

代码如下：

var  n,c,i,j,k:longint;maxn:real;a:array[0..101]of longint;p,f:array[-1..101,-1..101]of real;beginreadln(n,c);a[0]:=1;for i:=1 to n dobeginread(a[i]);for j:=0 to c div a[i] do read(p[i,j]);readln;end;f[0,0]:=1;for i:=0 to n dofor j:=0 to c dofor k:=0 to j div a[i] doif f[i,j]<f[i-1,j-k*a[i]]*p[i,k] thenf[i,j]:=f[i-1,j-k*a[i]]*p[i,k];maxn:=0;for i:=1 to c doif f[n,i]>maxn then maxn:=f[n,i];write(maxn:0:4);
end.

这篇关于SSL 1635——系统可靠性的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---