这道题是道很基本的0/1背包的问题,为了使解题很简单一点,可以将题目中要求的最大概率转换成不能录取的最小概率,这样1-dp[n]即为至少有一个offer的最大概率。状态方程
为:dp[j]=min{dp[j],dp[j-price[i]]*chance[i]};
#include"iostream"
#include"stdio.h"
#include"algorithm"
#include"string.h"
#include"cmath"
#include"queue"
#define mx 10005
using namespace std;
int price[mx];
double chance[mx];
double dp[mx];
int main()
{
int n,m,i,j,k;
while(cin>>n>>m,n||m)
{
for(i=;i<=m;i++)
{
cin>>price[i]>>chance[i];
chance[i]=-chance[i];
}
for(i=;i<=n;i++) dp[i]=;
for(i=;i<=m;i++)
{
for(j=n;j>=price[i];j--)
{
if(dp[j]>dp[j-price[i]]*chance[i])dp[j]=dp[j-price[i]]*chance[i];
}
}
printf("%.1lf%%\n",(-dp[n])*);
}
return ;
}