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

题意：Speakless现在有n万美元，他想申请出国，每个学校都有不同的申请费用a，Speakless得到这个学校offer的可能性b。求Speakless至少收到一份offer的可能性最大是多少。
思路：至少收到一份offer的可能性最大是多少不好求，可以转化为求一分都收不到的可能性最小是多少。这样就可以用01背包来解决了~
注意：概率是相乘而不是相加；
            因为求最小值，所以需要将数组f的初值置为1（因为概率最大就是1，一个都不选的时候收不到的概率也是1）。
[cpp]
#include<stdio.h>

#define maxn 11111

double f[maxn];

int main()
{
    int m,n,w[maxn];
    double v[maxn];
    while(scanf("%d %d",&n,&m)&&(n||m))
    {
        int i,j;
        for(i=1;i<=m;i++)
        {
            scanf("%d %lf",&w[i],&v[i]);
            v[i]=1-v[i];//因为要计算一个都收不改的概率，所以储存收不到offer的概率
        }
        for(i=0;i<=n;i++)
            f[i]=1;//初值置为1
        for(i=1;i<=m;i++)
            for(j=n;j>=w[i];j--)
                if(f[j]>f[j-w[i]]*v[i])//求最小值
                    f[j]=f[j-w[i]]*v[i];
        printf("%.1lf%%\n",100*(1-f[n]));
    }
    return 0;
}

作者：sdc1992

补充：软件开发 , C++ ,