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;
}
补充：软件开发 , C++ ,
