HUD 2955 Robberies [0-1背包的简单转化]

本文主要是介绍HUD 2955 Robberies [0-1背包的简单转化]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

/*Hud 2955 Robberies简单的0-1背包转换.由此题，抽象的事物也可以相当形象的解释.形象的解释，看以下注释.
*/
#include<stdio.h>
#include<string.h>
#define max(a,b) a>b?a:b
main()
{int T;scanf("%d",&T);while(T--){int i,n,v[105],V=0;double p,w[105],dp[10005];scanf("%lf%d",&p,&n);memset(dp,0,sizeof(dp));for(i=1;i<=n;i++){scanf("%d%lf",&v[i],&w[i]);w[i]=1.0-w[i];V+=v[i];}//被抓概率可以转换成安全概率(这样更易于计算).//其他金额初始为最危险的所以概率全为0；//抢劫的金额为0时，肯定是安全的，所以d[0]=1;dp[0]=1;for(i=1;i<=n;i++){for(int j=V;j>=v[i];j--)dp[j]=max(dp[j],dp[j-v[i]]*w[i]);}for(i=V;i>=1;i--)if(1-dp[i]<p) break;//Roy的安全概率大于1-P时都是安全的。printf("%d\n",i);}
}

这篇关于HUD 2955 Robberies [0-1背包的简单转化]的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---