UVa 11658

0-1 knapsack problem...

/* UVas */
/*****************************************************************************/
#define N 101
#define M 10001
int n, idx, x, y;
int h[N];
int d[M];
int main(void) {
    while (scanf("%d %d", &n, &idx)>0&&n) {
        for (int i=1; i<=n; i++) {
            scanf("%d.%d", &x, &y), h[i]=x*100+y;
        }
        int me=h[idx];
        memset(d, 0, sizeof(d));
        d[me]=1;
        for (int i=1; i<=n; i++) {
            if (i==idx) continue;
            for (int j=M-1; j>=h[i]; j--)
                d[j]|=d[j-h[i]];
        }
        double r=0;
        for (int i=5001; i<M; i++)
            if (d[i])
                r=max(r, (me/(double)i)*100);
        printf("%.2lf\n", r);
    }
}
/*****************************************************************************/