这是动态规划之01背包。
与01背包所不一样的是它的花费价值是浮点型的，所以状态改为dp[i]代表获得i的价值需要(double)dp[i]的代价，由此可知得到答案时反向遍历（优化时间复杂度），并且输出的是i这个变量。
这题计算的是概率，所以dp更新时用乘法而不是加法。
#include<bits/stdc++.h> using namespace std; const int N=50005; int t,M,m[N]; double P,p[N],ans[N]; int main() { scanf("%d",&t); while(t--) { scanf("%lf%d",&P,&M); int sum=0; for(int i=0;i<M;i++) { scanf("%d%lf",&m[i],&p[i]); sum+=m[i]; } memset(ans,0,sizeof(ans)); ans[0] = 1; for(int i=0;i<M;i++) for(int j=sum;j>=m[i];j--) ans[j]=max(ans[j],ans[j-m[i]]*(1-p[i])); for(int i=sum;i>=0;i--) if(ans[i]>(1-P)) { printf("%d\n",i); break; } } return 0; }
原文：https://www.cnblogs.com/Siv0106/p/11715456.html