Posted on 2011-09-09 13:47
成幸毅 阅读(240)
评论(0) 编辑 收藏 引用
总结:可以从这里知道,0-1背包问题,价值和重量可以交换,对于其中只要一个为整型就可以解决
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
const int MAXN = 110;
double f[100000];
int w[MAXN];
double v[MAXN];
int main() 
{
int cas;
scanf("%d",&cas);
while(cas--) {
double p;
int n;
scanf("%lf%d",&p,&n);
int sum = 0;
for(int i = 0; i < n; i++) {
scanf("%d%lf",&w[i],&v[i]);
sum += w[i];
}
memset(f,0,sizeof(f));
f[0] = 1;
for(int i = 0; i < n; i++)
for(int j = sum; j >= w[i]; j--) {
f[j] = max(f[j],f[j-w[i]]*(1-v[i]));
}
for(int j = sum; j >= 0; j--) {
if(f[j] > 1 - p) {
cout<<j<<endl;
break;
}
}
}
// system("pause");
return 0;
}