Question

杭电2995背包问题，求大神帮我改下，讲下解题思路，谢谢http://acm.hdu.edu.cn/showproblem.php?pid=2955

#include<iostream>
#include<cstdio>
#include<string.h>
//#define max(a,b) (a)>(b)?(a):(b)
using namespace std;

int max(int a,int b)
{
return a>b?a:b;
}

int main()
{
int t,m[110],n,f[11100],h[110],v;
float p,pi[110],v1,h1[110];
scanf("%d",&t);
while(t--)
{
memset(f,0,sizeof(f));
scanf("%f%d",&p,&n);
int i;
v1=p*100;
v=(int)v1;
//printf("%d \n",v);
for(i=1;i<=n;i++){
scanf("%d%f",&m[i],&pi[i]);
h1[i]=pi[i]*100;
h[i]=(int)h1[i];
// printf(" %d \n",h[i]);
}

for(i=1;i<=n;i++)
for(int j=v;j>=h[i];j--)
f[j]=max(f[j],f[j-h[i]]+m[i]);
printf("%d\n",f[v]);

}
return 0;
}

Answer 1

#include<iostream>
#include<cstdio>
#include<string.h>
//#define max(a,b) (a)>(b)?(a):(b)
using namespace std;

int main()
{
int t,m[110],n;
double f[11100];
double p,pi[110];
scanf("%d",&t);
while(t--)
{
memset(f,0,sizeof(f));
scanf("%lf%d",&p,&n);
int i;
int sum = 0;
//printf("%d \n",v);
for(i=1;i<=n;i++){
scanf("%d%lf",&m[i],&pi[i]);
// printf(" %d \n",h[i]);
sum += m[i];
}
for(i=1;i<=sum;i++) f[i] = 1;
f[0] = 0;
for(i=1;i<=n;i++)
for(int j=sum;j>=m[i];j--)
f[j]=min(f[j],1-(1-f[j-m[i]])*(1-pi[i]));
for(i=sum;i>=0;i--)
{
if(f[i]<=p)
{
printf("%d\n",i);
break;
}
}
}
return 0;
}