01背包乘法，以前是讀foreverlin的代碼A的，今天才算搞明白一點(diǎn)了。
#include <stdio.h>
#include <string.h>
#define N 10005
#define M 1005
#define MIN(a, b) (a < b ? a : b)
int a[M];
double b[M], f[N];
int main()
{
int n, m;
while(scanf("%d %d", &n, &m), n + m)
{
for(int i = 0; i < m; i++)
{
scanf("%d %lf", &a[i], &b[i]);
b[i] = 1 - b[i];
}
for(int i = 0; i <= n; i++) f[i] = 1;
for(int i = 0; i < m; i++)
{
for(int j = n; j >= a[i]; j--)
{
f[j] = MIN(f[j], f[j - a[i]] * b[i]);
}
}
printf("%.1lf%%\n", (1 - f[n]) * 100);
}
return 0;
}