input: amount of each receipt (yuan), output: max credit <= 100.0 yuan using some of the receipts

roundto100-optimized.c

#include<stdio.h>
#include<math.h>
#define MAX 1000
#define MAX_ITEMS 100
int main() {
    int i, j;
    int n = 0, w[MAX_ITEMS+1] = {0};
    int s[MAX+1] = {1};
    float weight;
    while (scanf("%f", &weight) != EOF) {
        w[++n] = round(weight * 10);
    }
    for (i=1; i<=n; i++)
        for (j = MAX; j >= w[i]; j--) {
            if (s[j] == 0 && s[j - w[i]] != 0)
                s[j] = i;
        }

    for (i=MAX; i>0; i--)
        if (s[i] != 0)
            break;
    printf("Max: %f\n", i / 10.0);
    fflush(stdout);
    while (i != 0) {
        printf("Use #%d: %f\n", s[i], w[s[i]] / 10.0);
        i = i - w[s[i]];
    }
    return 0;
}

Sample input:
20.3
44.7
29.7
24.1
34.2
23
10.7
13.2
10.9
19.1
18.6
9.9
9.9
16.8

Sample output:
Max: 100.000000
Use #9: 10.900000
Use #4: 24.100000
Use #2: 44.700000
Use #1: 20.300000