这题,简单的01背包问题。
只是一开始没有想到,觉得这题莫名其妙的。还是太水。
下面的是AC的代码:
#include <iostream>#include <cstdio>using namespace std;class data{public:int cost;double pre;};data Da[10005];double dp[10005];//拿到offer的概率int M, N;double max(double a, double b){return a > b ? a : b;}void DP(){for(int i = 0; i < M; i++){for(int j = N; j >= Da[i].cost; j–)//不断更新拿到的概率{dp[j] = max(dp[j], 1 – (1 – dp[j – Da[i].cost]) * (1 – Da[i].pre));}}}int main(){while(cin >> N >> M && (M + N)){for(int i = 0; i < M; i++)cin >> Da[i].cost >> Da[i].pre;for(int j = 0; j <= N; j++)dp[j] = 0;DP();printf("%.1lf%%\n", dp[N] * 100);}return 0;}
,伟人所达到并保持着的高处,并不是一飞就到的,