hdu 1203

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1203

思路：01背包问题，求一份都拿不到的概率，状态转移方程dp[j]=min(dp[j],dp[j-val[i]]*p[i])

p[i]表示得不到的概率,(1-dp[j])为花费j元得到Offer的最大概率

 1 #include<stdio.h>
 2 #include<string.h> 
 3 #include<iostream>
 4 #include<math.h>
 5 using namespace std;
 6 
 7 int val[10005];
 8 double dp[10005],p[10005];
 9 
10 double min(double a,double b)
11 {
12     if(a>b)
13     return b;
14     return a;
15 }
16 
17 int main()
18 {
19     int n,m;
20     while(scanf("%d %d",&n,&m),n+m)
21     {
22         for(int i=1;i<=m;i++)
23         {
24             scanf("%d %lf",&val[i],&p[i]);
25             p[i]=1-p[i];
26             
27         }
28         
29         for(int i = 0;i<=n;i++)
30             dp[i] = 1.0;
31             
32         for(int i=1;i<=m;i++)
33         {
34             for(int j=n;j>=val[i];j--)
35             {
36                 dp[j]=min(dp[j],dp[j-val[i]]*p[i]);
37             }
38         }
39         printf("%.1lf%%
",(1-dp[n])*100);
40     }
41     return 0;
42 }