hdu 1203 （01背包，灵活运用）

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

/***************************
 1. 01 背包
 2. 求至少一个的概率p，则先求全部没有的q ，最后1-q
 3. 要使p最大，则需q最小，（价值最小） 
 4. q 等于放入背包所有 物品的价值的 乘积 
 
# 2013-11-23 12:29:07  
# Time: MS   Memory: K
# Author: zyh
***************************/ 
#define N 10005
#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
using namespace std;

int c[N];//重量
double w[N]; //价值
double f[N];  //N件物品可以放的最大价值 
bool mark[N]; //标记哪些物品放入背包
 
double zeroonepack(int V,int n)
{
	int i,j;	
	for(i=0;i<=V;i++) f[i]=1.0;
	for(i=0;i<n;i++)
		for(j=V;j>=c[i];j--)
			if(f[j]>f[j-c[i]]*w[i])
				f[j] = f[j-c[i]]*w[i];
	return 1-f[V];
} 
int main()
{
	int t,n,i,m;
	
	while(~scanf("%d%d",&n,&m),m||n){	
		for(i=0;i<m;i++){
			scanf("%d %lf",&c[i],&w[i]);
			w[i] = 1- w[i]; 
		}
		printf("%.1lf%%\n",zeroonepack(n,m)*100);
	}
	return 0; 
}