Можно ли улучшить мое рекурсивное решение для Knapsack?

Я пытаюсь решить проблему с рюкзаком, и это рекурсивное решение, которое я придумал. Можно ли это сделать лучше? Я думаю, мне нужно добавить запоминание, проверив, достиг ли я этого состояния раньше. Я прав, что мне нужно добавить состояние для state[c_w][i]?

Я намеренно не использовал динамическое программирование, так как знаю рекуррентные отношения для этого, а скорее хотел получить правильную рекурсию.

#include <stdio.h>

int memoize[1000][1000];
int max(int a, int b)
{
        return a>b?a:b;
}

/* c_w-current weight of the container */ 
int max_profit_func(int *val, int *wt, int W, int c_w, int i, int size)
{
        int max_profit = 0;
        int j;

        /* if the current item is beyond the range then we have 0 profit*/
        if (i >= size)
                return 0;
        if (memoize[c_w][i] != -1)
                return memoize[c_w][i];
        /* get the profit with this index and if the profit is more than previous
         * than store it */
        for(j=i;j<size;j++) {
                int profit = 0;
                if (c_w+wt[j] <= W)
                        profit = val[j] + max_profit_func(val, wt, W, c_w+wt[j], j+1, size);
                max_profit = max(max_profit, profit);
        }
        memoize[c_w][i] = max_profit;
        return max_profit;
}

int main(void) {
        int val[] = {3, 7, 2, 9};
        int wt[] = {2, 3, 4, 5};
        int W = 5;

        memset(memoize, -1, sizeof(int)*1000*1000);
        printf("%d\n", max_profit_func(val, wt, W, 0, 0, sizeof(wt)/sizeof(wt[0])));
        return 0;
}