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; }