本文共 1102 字，大约阅读时间需要 3 分钟。
题意很直观了， 中文题。
至少得到一份offer的概率就等于 1 - 一份offer都得不到的概率。
背包问题 ， 求得到offer概率最大，也就是一份都得不到的概率最小。
将每一份offer得不到的概率视为权值 ， 重量均为所投offer所用美元
那么dp[i] 就表示用了i美元时 ， 得不到offer的最小概率
最终结果就是1 - dp[n]
代码如下：
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 using namespace std;14 #define MAXN 1001015 #define INF 0x3f3f3f3f16 #define MOD 100000000717 #define eps 1e-618 #define LL long long19 double dp[MAXN];20 int w[MAXN];21 double v[MAXN];22 int n , m;23 void solve()24 {25 for(int i = 0; i < m; i ++)26 scanf("%d %lf",&w[i] , &v[i]);27 for(int i = 0; i <= n; i ++) dp[i] = 1;28 for(int i = 0; i < m; i ++)29 for(int j = n; j >= w[i]; j --)30 dp[j] = min(dp[j] , dp[j - w[i]] * (1.0 - v[i])); 31 printf("%.1lf%%\n",(1.0 - dp[n]) * 100);32 }33 34 int main()35 {36 while(scanf("%d %d",&n,&m) && (n+m))37 {38 solve();39 }40 return 0;41 }
转载于:https://www.cnblogs.com/By-ruoyu/p/4467642.html
