HDU-2955 Robberies【0-1リュックサック】

テーマリンク:http://acm.hdu.edu.cn/showproblem.php?pid=2955                                       Robberies                         Time Limit:2000/1000 MS(Java/Others)    メモリLimit:32768/32768 K(Java/Others)  Problem Description The aspiring Roy the Robbebebebebebes seen a lot of American movies、and knowththat the bad gguuuuuuugggh caght the end、oten because they become to gredddddy.He has dedededededededededededededededededededededededededettttttwowowoworererererererererereaaaaaaaaaaaaaaaaaatttttttttttttttttttttttworerererererererereiversity.                                                                    For a few moths now,Roy has been asessing the security of various banks and the amount of cash the Hold.He wants to make a cacaculated rik,and grab as much money.as possiblehas decided up on a tolerable probability of getting caugt.She feels that he is safe enough the banks he robs together give a probability less this.  Input  T he first line of input gives T,the number of cases.For each scenaro,the first line of inputgives a frototoint number P,the probability Roy neeeds to be below,and an integer N,thenumbebebers ininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininj contains Mj milions、and the probability of getting cagt from robbing it is Pj.  Output  For each test case、output a line with the maximnumber of milions he can expect to get while the probability of getting cagt less than the limit set.Notes and Containts 0Sample Input

3
0.04 3
1 0.02
2 0.03
3 0.05
0.06 3
2 0.03
2 0.03
3 0.05
0.10 3
1 0.03
2 0.02
3 0.05

Sample Output

2
4
6

問題を解く構想
この問題は容易に考えられます.最大の確率でバックパックの最大容量として、銀行を商品として、銀行の逮捕確率を商品体積として、銀行のお金を商品価格としています.これは二つの問題があります.①捕まった確率は浮動小数点で、小数点以下の何桁かが分からないので、配列が開けられません.②逮捕される確率は簡単に加算されません.
すべての銀行のお金の合計をバックパックの最大容量として、ある銀行のお金を奪って商品の体積として、この銀行を略奪した後の逃走確率を商品価値としてもいいです.小さい時から大きな荷物を数えると、商品価値(逃げる確率)が最小の逃走確率より大きい時に、対応するリュックサックの容量(お金)が得られます.
ACコード

#include 
#include 
#include 
using namespace std;
struct bank {
	double w;
	int c; 
}b[101];
double escape[10005];	//   i        
int main()
{
	int T,N;
	double P;
	cin >> T;
	while( T--)
	{
		cin >> P >> N;
		int sum=0;	//       
		for(int i=0;i> b[i].c >> b[i].w;
			sum += b[i].c; 
		}
		memset(escape,0,sizeof escape);	//          ，      
		escape[0] = 1;	//        ？         1  
		for(int i=0;i=b[i].c;j--)	//                   ，                  
				escape[j] = max(escape[j],escape[j-b[i].c]*(1-b[i].w));	//            ，              
		
		for(int i=sum;i>=0;i--)
			if(escape[i] > double(1-P)) {	//         
				cout << i << endl;
				break;
			} 
	}
}