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

roundto100.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_ITEMS+1][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 >= 0; j--) {
            if (j >= w[i] && s[i - 1][j - w[i]] != 0)
                s[i][j] = i;
            else
                s[i][j] = s[i-1][j];
        }

    for (i=MAX; i>0; i--)
        if (s[n][i] != 0)
            break;
    printf("Max: %f\n", i / 10.0);
    for (j=n; j>0; j--) {
        if (s[j][i] != s[j-1][i]) {
            printf("Use #%d: %f\n", s[j][i], w[s[j][i]] / 10.0);
            i = i - w[s[j][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 #14: 16.800000
Use #13: 9.900000
Use #12: 9.900000
Use #7: 10.700000
Use #6: 23.000000
Use #3: 29.700000