Knapsack_FPTAS.awk

## format of input
## first line; K (capacity of bin) , k (divider)
## for each line
## weight value
NR == 1 {
    K = $1;
    k = $2;
    for (j = 1;j <= K;j++) {
        dp [ j , 0 ] = 0;
    }
}
NR != 1 {
    i = NR - 1;
    w = $1 / k;
    v = $2;
    # dp[weight][item]
    dp[ 0 , i ] = 0;
    for (j = 1;j <= K;j++) {
        if (j - w > 0) {
            dp [ j , i ] = max( dp [ j , i - 1 ], dp [ j - w , i - 1 ] + v );
        } else {
            dp [ j , i ] = dp [ j , i - 1 ];
        }
    }
}
END {
    printf "result : %d\n" , dp [ K , NR - 1 ];
}
function max (a,b) {
    if (a > b) {
        return a;
    } else {
        return b;
    }
}