HDU 1203 I NEED A OFFER!

思路：簡單的01背包

   總費用看作背包容量，申請費用看作每個背包的重量，價值為至少有一份offer的概率

   狀態轉移方程：dp[j]=max(dp[j] , 1-(1-dp[j-a[i].val])*(1-a[i].p));

[cpp]
#include<stdio.h> 
#include<string.h> 
double dp[10001],t; 
struct node 
{ 
   int val; 
   double p; 
}a[10001]; 
int main() 
{ 
    int n,m,i,j; 
    while(scanf("%d%d",&n,&m)&&(n+m)) 
    { 
      for(i=0;i<m;i++) 
         scanf("%d%lf",&a[i].val,&a[i].p); 
         memset(dp,0,sizeof(dp)); 
         for(i=0;i<m;i++) 
          for(j=n;j>=a[i].val;j--) 
          { 
             if(dp[j]<(t=1-(1-dp[j-a[i].val])*(1-a[i].p))) 
              dp[j]=t; 
          } 
          printf("%.1lf%%\n",dp[n]*100); 
    } 
   return 0; 
}