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;
}

补充：软件开发 , C++ ,