这道题是道很基本的0/1背包的问题，为了使解题很简单一点，可以将题目中要求的最大概率转换成不能录取的最小概率，这样1-dp[n]即为至少有一个offer的最大概率。状态方程

为：dp[j]=min{dp[j],dp[j-price[i]]*chance[i]};

1 #include"iostream" 2 #include"stdio.h" 3 #include"algorithm" 4 #include"string.h" 5 #include"cmath" 6 #include"queue" 7 #define mx 10005 8 using namespace std; 9 int price[mx];10 double chance[mx];11 double dp[mx];12 int main()13 {14     int n,m,i,j,k;15     while(cin>>n>>m,n||m)16     {17         for(i=1;i<=m;i++)18         {19             cin>>price[i]>>chance[i];20             chance[i]=1-chance[i];21         }22         for(i=0;i<=n;i++) dp[i]=1;23         for(i=1;i<=m;i++)24         {25             for(j=n;j>=price[i];j--)26             {27                 if(dp[j]>dp[j-price[i]]*chance[i])dp[j]=dp[j-price[i]]*chance[i];28             }29         }30         printf("%.1lf%%\n",(1-dp[n])*100);31     }32     return 0;33 }