0-1背包

#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std;#define maxn 105 double p[maxn]; int m[maxn]; double DP[maxn*maxn];int main() {int T;scanf("%d",&T);while(T--){int i,j,N,sum;double P;scanf("%lf %d",&P,&N);P=1-P; sum=0;memset(DP,0,sizeof(DP)); DP[0]=1;for(i=1; i<=N; i++){scanf("%d%lf",&m[i],&p[i]);sum=sum+m[i];p[i]=1-p[i];}for(i=1; i<=N; i++)for(j=sum; j-m[i]>=0; j--)DP[j]=fmax(DP[j],p[i]*DP[j-m[i]]);for(i=sum; i>=0; i--){if(DP[i]-P>0){printf("%d\n",i);break;}}}return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/zufezzt/p/4646400.html

總結(jié)

以上是生活随笔為你收集整理的HDU 2955 Robberies的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。