HDOJ 1203 I NEED A OFFER!(01背包)

 1 #include<stdio.h>
 2 #include<string.h>
 3 int main()
 4 {
 5     int v[10001];
 6     double w[10001],f[10001];
 7     int n,m,i,j;
 8     while(scanf("%d %d",&n,&m)!=EOF&&n||m)
 9     {
10         for(i=0;i<=n;i++)
11         f[i]=1.0;
12         for(i=0;i<m;i++)
13         scanf("%d %lf",&v[i],&w[i]);
14         for(i=0;i<m;i++)
15         {
16             for(j=n;j>=v[i];j--)
17             {
18                 f[j]=f[j]<f[j-v[i]]*(1-w[i])?f[j]:f[j-v[i]]*(1-w[i]);
19             }
20         }
21         printf("%.1lf%%\n",(1-f[n])*100);
22         
23     }
24     return 0;
25 }