http://acm.hdu.edu.cn/showproblem.php?pid=1203

虽然是01背包问题，但是完全可以用贪心解决此题，如果用了动态，我认为反而把简单问题麻烦化了

此解法时间效率不高，有时间再重新看看……

#include<stdio.h>
int main()
{
    int m,n,a[1001],i,j,t;
    double b[1001],k[1001],t1,s;
    while(scanf("%d%d",&m,&n)!=EOF&&!(m==0&&n==0))
    {
        for(i=1;i<=n;i++)
        {
            scanf("%d%lf",&a[i],&b[i]);
            k[i]=b[i]/a[i];
        }
        for(i=1;i<n;i++)
            for(j=1;j<n-i;j++) if(k[j]>k[j+1]) {
                    t=a[j];a[j]=a[j+1];a[j+1]=t; t1=b[j];b[j]=b[j+1];b[j+1]=t1;
                    t1=k[j];k[j]=k[j+1];k[j+1]=t1;
                }
        s=1;
        for(i=n;i>=1;i--)
        {
            if(m>=a[i]){
                s*=1-b[i];
                m-=a[i];
            }
            else    break;
        }
        s=100*(1-s);
        printf("%.1lf%%\n",s);
    }
    return 0;
}