HDU 1203 I NEED A OFFER （01背包&&概率dp）

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=10005;
int n,m;
double dp[maxn],value[maxn];
int weight[maxn];
int main(){
   while(scanf("%d%d",&n,&m)!=EOF){
      if(n==0&&m==0)
        break;
    for(int i=1;i<=n;i++){
        dp[i]=1.0;
    }
    int cost;
    double p;
    for(int i=1;i<=m;i++){
        scanf("%d%lf",&weight[i],&p);
        value[i]=1-p;
    }
    dp[0]=1.0;
    for(int i=1;i<=m;i++){
        for(int j=n;j>=weight[i];j--){
            dp[j]=min(dp[j],dp[j-weight[i]]*value[i]);
        }
    }
    double ans=(1-dp[n])*100.0;
    printf("%.1lf%%\n",ans);

   }
   return 0;
}