暑期dp46道(34)--HDOJ 1203 01背包

题目链接：HDOJ 1203

题解：01背包问题，注意至少拿到一个offer的概率 b：一个offer拿不到的概率a,则b=1-a;

所以

dp[j] = Max(dp[j], 1-(1- dp[j - c[i]])*(1 - w[i]));

代码：

#include<cstdio> #include<cstring> #include<string> #define debug 0 #define M(a) memset(a,0,sizeof(a)) #define Max(a,b) ((a>b)?a:b) #define REP(o) for(int i=1;i<=o;i++) const int maxn = 10000 + 5; int n, m; int c[maxn]; double w[maxn], dp[maxn]; void Do() { for (int i = 1; i <= n; i++) for (int j = m; j >= c[i]; j--) { dp[j] = Max(dp[j], 1 - (1 - dp[j - c[i]])*(1 - w[i])); } printf("%.1f%%\n", 100 * dp[m]); } int main() { #if debug freopen("in.txt", "r", stdin); #endif//debug while (~scanf("%d%d", &m, &n)) { if (n == 0 && m == 0) break; M(dp); REP(n) { scanf("%d%lf", &c[i], &w[i]); } Do(); } return 0; }