hdu 2599 Robberies

이 문제는 나도 어이가 없다. 나도 지장과 같다.매우 뚜렷한 01가방 제목이지만 주의해야 할 것은 이 확률은 곱해서 얻은 탈출 확률이지 직접적으로 덧붙이는 것이 아니다. 그리고 마지막으로 정밀도를 주의해야 한다. 나도 시야를 봤다. 바로 이 WA3회 때문이다.
제목 링크:https://vjudge.net/problem/HDU-2955

#include 
#include 
#include 

using namespace std;

const int inf = 0x3f3f3f3f;
const int maxn = 105;
double sum;
int cntn , s;
double dp[10005];

struct Bank {
	double risk;
	int money;
	Bank (double a=0 , int b=0) : risk(a),money(b) {}
}bank[maxn];

void solve () {
	for (int i = 1 ; i <= s ; i++)
		dp[i] = -1000000;
	dp[0] = 1;
	for (int i = 1 ; i <= cntn ; i++) {
		for (int j = s ; j >= bank[i].money ; j--)
			dp[j] = max(dp[j] , dp[j-bank[i].money]*bank[i].risk);
	} 
	for (int i = s ; i >= 0 ; i--)
		if (dp[i] - (1-sum) > 0.000000001) {
			printf("%d
", i);
			break;
		}
}

int main () {
	int ncase;
	scanf("%d" , &ncase);
	while (ncase--) {
		memset(bank, 0, sizeof(bank));
		s = 0;
		scanf("%lf %d" , &sum , &cntn);
		for (int i = 1 ; i <= cntn ; i++) {
			double risk;
			int money;
			scanf("%d %lf" , &money , &risk);
			bank[i] = Bank(1-risk , money);
			s += money;
		}
		solve();
	}
}