Knapsack Problem

Solution: Below is the code using dynamic programming,

#define MAX(a,b) (a)>(b)?(a):(b)
/*
 * Number of objects = 4
 * Capacity ig Knapsack = 8
 */
#define N 4
#define W 8
typedef struct {
    int32_t v;
    int32_t w;
} Object;

Object obj[N+1] = {{0, 0}, {15, 1}, {10, 5}, {9, 3}, {5, 4}};
int32_t V[N+1][W+1] = {0, };

int main()
{
    int32_t n = 0;
    int32_t w = 0;
    int32_t value = 0;
    int32_t weight = 0;

    for(n=1; n<=N; n++) {
        for(w=0; w<=W; w++) {
            weight = obj[n].w;
            value = obj[n].v;

            /*
             * Cases:
             * - Last item is excluded from the final set: V[n-1][w]
             * - Last item is included in the final set: value + V[n-1][w-weight]
             *
             * Corner case:
             * - If weight > w, choose V[n-1][w]
             */
            if(w >= weight) {
                V[n][w] = MAX( V[n-1][w], value + V[n-1][w-weight] );
            }
            else {
                V[n][w] = V[n-1][w];
            }
        }
    }

    printf("Ans = %d\n", V[N][W]);
    return 0;
}