Come contare le combinazioni non maggiori di un dato volume in un problema dello zaino?

Question

Ti viene dato un certo set di oggetti con peso WI e il volume della borsa.

Caso:

Input: 

3 (count of items) 10 (volume of the bag)
1 2 4 (weight for each item)

Output

8 (since you can put any item in or not 2 * 2 *2)

Ho una soluzione ingenua usando DFS come

public class Main {
    public static void main(String... args) throws Exception {
        Scanner scanner = new Scanner(System.in);
        int size = scanner.nextInt();
        int volume = scanner.nextInt();
        int[] weights = new int[size];
        for (int i = 0; i < size; ++i) weights[i] = scanner.nextInt();
        System.out.println(getCounts(weights, 0, volume));
    }

    private static int getCounts(int[] nums, int pos, int target) {
        if (target < 0) return 0;
        if (pos >= nums.length) return 1;
        return getCounts(nums, pos+1, target) +
            getCounts(nums, pos+1, target-nums[pos]);
    }
}

Come previsto, ha prodotto TLE e ho aggiunto la cache per evitare il ricalculation come

public class Main {
    private static int[][] cache;
    public static void main(String... args) throws Exception {
        Scanner scanner = new Scanner(System.in);
        int size = scanner.nextInt();
        int volume = scanner.nextInt();
        cache = new int[size+1][volume+1];
        for (int i = 0; i <= size; ++i) {
            for (int j = 0; j <= volume; ++j) {
                cache[i][j] = -1;
            }
        }
        int[] weights = new int[size];
        for (int i = 0; i < size; ++i) weights[i] = scanner.nextInt();
        System.out.println(getCounts(weights, 0, volume));
    }

    private static int getCounts(int[] nums, int pos, int target) {
        if (target < 0) return 0;
        if (pos == nums.length) return 1;
        if (cache[pos][target] != -1) return cache[pos][target];
        int count = getCounts(nums, pos+1, target) +
            getCounts(nums, pos+1, target-nums[pos]);
        cache[pos][target] = count;
        return count;
    }
}

Ma l'OJ mi chiede di errore di memoria mentre la memoria è all'interno del limite => 13064K <32768K, hai idea di risolvere questo problema?

1. Perché non ha fallito?
2. Per questo potrebbe essere trovata una soluzione DP senza backtracking?

Qualsiasi aiuto sarà apprezzato :)

Ecco il Problema originale in cinese.