hdu 1203 I NEED A OFFER!

hdu 1203 I NEED A OFFER!

大家好,又见面了,我是全栈君。

I NEED A OFFER!

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 15503    Accepted Submission(s): 6128
Problem Description
Speakless非常早就想出国,如今他已经考完了全部须要的考试。准备了全部要准备的材料。于是,便须要去申请学校了。要申请国外的不论什么大学。你都要交纳一定的申请费用,这但是非常惊人的。Speakless没有多少钱,总共仅仅攒了n万美元。他将在m个学校中选择若干的(当然要在他的经济承受范围内)。每一个学校都有不同的申请费用a(万美元),而且Speakless预计了他得到这个学校offer的可能性b。不同学校之间是否得到offer不会互相影响。“I NEED A OFFER”,他大叫一声。帮帮这个可怜的人吧,帮助他计算一下,他能够收到至少一份offer的最大概率。

(假设Speakless选择了多个学校,得到随意一个学校的offer都能够)。

 


Input
输入有若干组数据,每组数据的第一行有两个正整数n,m(0<=n<=10000,0<=m<=10000)
后面的m行,每行都有两个数据ai(整型),bi(实型)分别表示第i个学校的申请费用和可能拿到offer的概率。
输入的最后有两个0。

 


Output
每组数据都相应一个输出,表示Speakless可能得到至少一份offer的最大概率。用百分数表示,精确到小数点后一位。
 


Sample Input
   
   
10 3 4 0.1 4 0.2 5 0.3 0 0

 


Sample Output
   
   
44.0%
Hint
You should use printf("%%") to print a '%'.

 


思路:01背包问题。要求得到至少一份offer的最大概率,能够转化为求都得不到offer的最小概率。

#include <stdio.h>
#include <iostream>
#include<algorithm>
using namespace std;
#define N 100005
double dp[N];
struct node
{
	int x;
	double y;
}a[N];

double min(double a,double b)
{
	return a<b?

a:b;}int main(){ int n,m; int k,i,j; while(cin>>n>>m) { if(n==0&&m==0) break; for(i=0;i<m;i++) { cin>>a[i].x>>a[i].y; a[i].y=1-a[i].y; // 得不到offer的概率 } for(i=0;i<=n;i++) dp[i]=1; for(i=0;i<m;i++) { for(j=n;j>=a[i].x;j--) { dp[j]=min(dp[j-a[i].x]*a[i].y,dp[j]); // 要么选这座大学 得不到offer (dp[j-a[i].x]*a[i].y)。要么选这座大学得到offer (dp[j]) } } printf("%.1lf%%\n",(1-dp[n])*100); } return 0;}

 
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/116669.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号