HDOJ 1203
题意：Speakless现在有n万美元，他想申请出国，每个学校都有不同的申请费用a，Speakless得到这个学校offer的可能性b。求Speakless至少收到一份offer的可能性最大是多少。
思路：至少收到一份offer的可能性最大是多少不好求，可以转化为求一分都收不到的可能性最小是多少。这样就可以用01背包来解决了~
注意：概率是相乘而不是相加；
因为求最小值，所以需要将数组f的初值置为1（因为概率最大就是1，一个都不选的时候收不到的概率也是1）。
01背包问题，注意概率是乘就好。
#include<iostream>
#include<cstring>
using namespace std;int m,n,w[10010];
double dp[10010],v[10010];
void init(){memset(dp,0,sizeof(dp));memset(v,0,sizeof(v));memset(w,0,sizeof(w));
}
int main(){while(cin>>n>>m){init();if(n==0 &&m==0) break;for(int i=1;i<=m;i++){cin>>w[i]>>v[i];v[i]=1-v[i];}for(int i=0;i<=n;i++){dp[i]=1; //概率最大为1 }for(int i=1;i<=m;i++){for(int j=n;j>=w[i];j--){if(dp[j]>dp[j-w[i]]*v[i])dp[j]=dp[j-w[i]]*v[i];}}printf("%.1lf%%\n",100*(1-dp[n]));}return 0;
}