hdu 1203 I NEED A OFFER!(확률 dp)

http://acm.hdu.edu.cn/showproblem.php?pid=1203
대립 사건 을 구하 다.하나 도 받 지 못 한 최소한 의 확률 을 구하 다.

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;

double dp[10010],w[10010];
int cost[10010];

int main()
{
	int n,m;
	while(~scanf("%d %d",&n,&m))
	{
		if(n == 0 && m == 0) break;

		for(int i = 1; i <= m; i++)
			scanf("%d %lf",&cost[i],&w[i]);

		for(int i = 0; i <= n; i++)
			dp[i] = 1.0;

		for(int i = 1; i <= m; i++)
		{
			for(int j = n; j >= cost[i]; j--)
			{
				dp[j] = min(dp[j],dp[j-cost[i]]*(1-w[i]));
			}
		}
		printf("%.1lf%%
",(1-dp[n])*100);
	}
	return 0;
}