hdu 2955 Robberies（背包變形）

這道題麻煩的是概率這東西沒法用個循環表示出來，根據我以往的經驗，指望著把給出的測試數據乘上一百或者一萬這種方法是完全不可取的。

乍一看，這道題目是拿概率當包，因為概率是浮點數，如果是想像普通背包一樣處理，那是完全行不通的。

但是把題目轉換一下，題目給出的概率是被抓的概率，我們可以把所有銀行能搶的錢的總和當成一個包，把概率轉換為安全概率，很容易理解這個包最後一定是能裝滿的，我們包裡面的財富是什麼？是概率！安全的概率！

從包的最大值往下查，找到第一個包裡面裝的安全概率可以讓我們滿意，這就是我們想要的結果。

動態規劃的題目很有意思，有很多非常經典的問題，但是也正是因為經典問題太多了，圍繞著這些經典問題，就有了很多經典的資料。材料多的好處是學起來相對容易了很多，壞處是有時候題目掩蓋了思想的本質。而且DP問題也太花樣繁多了，有些簡直就是無厘頭了。

#include<stdio.h>
#include<string.h>
#define N 105
double w[N];
int v[N];
double dp[10005];
double Max(double a,double b)
{
	if(a>b)
		return a;
	else
		return b;
}
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		double vt;
		int n;
		int i,j;
		scanf("%lf%d",&vt,&n);
		int sum=0;
		for(i=0;i<n;i++)
		{
			scanf("%d%lf",&v[i],&w[i]);
			sum+=v[i];
			w[i]=1-w[i];
		}
		for(i=0;i<=sum;i++)
			dp[i]=0;
		dp[0]=1;
		for(i=0;i<n;i++)
		{
			for(j=sum;j>=v[i];j--)
				dp[j]=Max(dp[j],dp[j-v[i]]*w[i]);
		}
		vt=1-vt;
		for(i=sum;i>=0;i--)
		{
			if(dp[i]>vt)
			{
				printf("%d\n",i);
				break;
			}
		}
	}
	return 0;
}