DP问题。
#include <stdio.h> #define MAXNUM 10002 int main() {
int m, n;
int cost[MAXNUM]; // the Cost for every school
float prob[MAXNUM]; // the probality for every school
float probs[MAXNUM]; // the probality for All-amount-money
int i, j; while ( scanf("%d %d", &n, &m)!=EOF && (m||n)) {
for (i=; i<m; ++i) {
scanf("%d %f", &cost[i], &prob[i]);
prob[i] = 1.0f - prob[i];
} for (i=; i<=n; i++)
probs[i] = 1.0f; for (i=; i<m; ++i) {
for (j=n; j>=cost[i]; --j) {
if (probs[j-cost[i]] * prob[i] < probs[j])
probs[j] = probs[j-cost[i]] * prob[i];
}
} printf("%.1f%%\n", (1.0f-probs[n])*100.0f);
} return ;
}