View Code // 从反面考虑：就是一个offer都没获得,最后结果p=1-p; #include " iostream " #include " algorithm " using namespace std; struct offer{ int a; double b;}s[ 10000 ]; int cmp(offer x, offer y){ return x.b > y.b;} int main(){ int n,m; int i; while (cin >> n >> m,n + m) { for (i = 0 ;i < m;i ++ ) scanf( " %d %lf " , & s[i].a, & s[i].b); sort(s,s + m,cmp); int sum = 0 ; double p = 1.0 ; for (i = 0 ;i < m;i ++ ) { if (s[i].a + sum <= n) { sum += s[i].a; p *= ( 1 - s[i].b); } } p = ( 1 - p) * 100 ; printf( " %.1lf%%\n " ,p); } return 0 ;} 这题有漏洞啊！应该是属于背包问题，贪心也不可能这么容易过啊！
不多解释，看错误的一种情况：
sample:
>10 4
>5 0.4
>4 0.3
>3 0.2
>2 0.2
很明显 P2+P3=0.4>P4=0.3
而运行结果为：58.0%
正确结果：61.6%
所以此题还是选择背包算法求解好！
View Code #include " iostream " using namespace std; double dp[ 100001 ]; struct node{ int a; double b;}s[ 1001 ]; double Max( double a , double b){ return a > b ? a:b;} int main(){ int n,m; int i,j; while (cin >> n >> m,n + m) { for (i = 0 ;i < m;i ++ ) scanf( " %d %lf " , & s[i].a, & s[i].b); memset(dp, 0.0 , sizeof (dp)); for (i = 0 ;i < m;i ++ ) { for (j = n;j >= s[i].a;j -- ) { dp[j] = Max(dp[j] , 1 - ( 1 - dp[j - s[i].a]) * ( 1 - s[i].b)); } } double p = dp[n] * 100 ; printf( " %.1lf%%\n " ,p); } return 0 ;}