hdu 1203 I NEED A OFFER!（0/1背包）

继续0/1背包。只是需要小小的转化一下，因为他求的是至少被录取的最大概率。dp[j]=max(dp[j],1-(1-dp[j-m[i]])*(1-r[i]));

#include<iostream>using namespace std;double dp[10005];double r[1010];int m[1010];double max(double a,double b){ return a>b?a:b;}int main(){ int n,i,j,sum; while(scanf("%d%d",&sum,&n)!=EOF) { if(sum==0&&n==0) break; memset(dp,0,sizeof(dp)); for(i=0;i<n;i++) scanf("%d%lf",&m[i],&r[i]); for(i=0;i<n;i++) { for(j=sum;j>=m[i];j--) dp[j]=max(dp[j],1-(1-dp[j-m[i]])*(1-r[i])); } printf("%.1f%%\n",dp[sum]*100); } return 0;}