首页 > 其他 > 详细

HDU - 2955

时间:2017-08-22 01:07:09      阅读:314      评论:0      收藏:0      [点我收藏+]

HDU - 2955

 

还是01背包问题,只是这里是与概率有关的问题,所以在选取两件物品时概率是相乘的而不是相加

 

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 struct bag {
 8     int v;
 9     double p;
10 } Bag[10010];
11 double dp[10010];
12 
13 int main(int argc, const char * argv[]) {
14     
15     int N, T;
16     double sfp;
17     scanf("%d", &T);
18     while (T--) {
19         scanf("%lf%d", &sfp, &N);
20         int sum = 0;
21         for (int i = 0; i < N; i++) {
22             scanf("%d%lf", &Bag[i].v, &Bag[i].p);
23             sum += Bag[i].v;
24         }
25         memset(dp, 0, sizeof(dp));
26         dp[0] = 1;//此时安全概率
27         for (int i = 0; i < N; i++) {
28             for (int j = sum; j >= Bag[i].v; j--) {
29                 dp[j] = max(dp[j], dp[j - Bag[i].v] * (1 - Bag[i].p));//概率应该相乘
30             }
31         }
32         for (int i = sum; i >= 0; i--) {
33             if (sfp > 1 - dp[i]) {
34                 printf("%d\n", i);
35                 break;
36             }
37         }
38     }
39     return 0;
40 }

 

HDU - 2955

原文:http://www.cnblogs.com/xFANx/p/7407436.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!