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;
}