Speakless没有多少钱，总共仅仅攒了n万美元。他将在m个学校中选择若干的（当然要在他的经济承受范围内）。每一个学校都有不同的申请费用a（万美元）。而且Speakless预计了他得到这个学校offer的可能性b。不同学校之间是否得到offer不会互相影响。“I NEED A OFFER”，他大叫一声。
帮帮这个可怜的人吧。帮助他计算一下，他能够收到至少一份offer的最大概率。（假设Speakless选择了多个学校，得到随意一个学校的offer都能够）。
用百分数表示。精确到小数点后一位。
10 3 4 0.1 4 0.2 5 0.3 0 0
44.0%
#include<iostream>
#include<cstring>
using namespace std;
int a[10005];
double b[10005];
double d[10005];
int main()
{
int n,m;
while(~scanf("%d%d",&n,&m))
{
if(n==0 && m==0) break;
int i,j;
for(i=1;i<=m;i++)
{
scanf("%d%lf",a+i,b+i);
b[i]=1-b[i];
}
for(i=0;i<=n;i++)
d[i]=1;
double min=1.1;
for(i=1;i<=m;i++)
{
for(j=n;j>=a[i];j--)
if(d[j]>d[j-a[i]]*b[i])
d[j]=d[j-a[i]]*b[i];
}
printf("%.1lf%c\n",(1-d[n])*100,'%');
}
return 0;
}原文：http://www.cnblogs.com/liguangsunls/p/7244137.html