HDU2955_Robberies_01背包变种

题目大意：         一个人去偷n家银行偷东西，每家银行规定只能选择偷or不偷，然后偷了的话，有一个被捉到的概率。然后这个小偷的老妈给他算了一下，只要他能够让他被捉的概率小于一个指定值ans_p,那么他就不会被捉，然后求他不被捉的能偷到的最大价值。 解题思路：        根据概率方面的知识，要求一个人被捉的概率，其实应该先算出偷每家银行不被捉到的概率，然后将他偷几家银行的不被捉的概率求乘积。最后再用1减去这个数即为他偷了这几家银行，被捉的概率。概率是实数，无法做背包，用银行的总钱数做背包即可。

#include
#define max(x,y) x>y? x:y
const int MAX=10005;
using namespace std;
int main(void)
{
	int cas;
	cin>>cas;
	while(cas--)
	{
		int i,tal,n,j;
		int v[MAX];
		double p[MAX],dp[MAX],ans_p;
		
		cin>>ans_p>>n;
		tal=0;
		for(i=1;i<=n;i++)
		{
			cin>>v[i]>>p[i];
			p[i]=1.0-p[i];
			tal+=v[i];
		}
		for(i=0;i=0;j--)
			{
				dp[j]=max(dp[j],dp[j-v[i]]*p[i]);
			}
		for(i=tal;i>=0;i--)//从大到小，第一个满足就输出
		{
			if(dp[i]>1-ans_p)
			{
				cout<