1
$\begingroup$

You are given a certain set of items with weight wi and the volume of the bag.

Case:

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)

I have a naive solution using DFS as


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]);
    }
}

As expected, it produced TLE and I added cache to avoid re-calculation as

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;
    }
}

But the OJ prompt me of memory error while the memory is within the limit => 13064K < 32768K, any idea to solve this issue?

  1. Why did it fail?
  2. Could a DP solution without backtracking be found for this?

Any help will be appreciated :)

Here is the original problem in Chinese.

$\endgroup$
  • 2
    $\begingroup$ Could you please add a reference to the original problem? 1) Credit should be attributed. 2) The original problem is probably stated clearer with more utilities. For example, people can submit solutions to the online judge. 3) A reference is apt to motivate people. 4) A reference may save readers who look for related materials lots of time. 5) Many of us prefer not to spoil an ongoing programming contest. $\endgroup$ – John L. Apr 17 '19 at 2:41
  • $\begingroup$ Yes, of course. But there is a problem about the language. It's just an online practice. $\endgroup$ – Hearen Apr 17 '19 at 2:56
  • 2
    $\begingroup$ We're not a coding site, and some people here don't read C code. Please replace the code with a concise description of the algorithm (maybe short pseudocode). Also, please state the problem in the body of your post using full sentences. A summary in the title is not a substitute for a clear description of the problem in the body of your post. We probably can't tell you why your code uses too much memory (that's off-topic here), but we might be able to answer a question about the space complexity of algorithms for this problem. $\endgroup$ – D.W. Apr 17 '19 at 6:41
  • $\begingroup$ this is java, sorry to say this...I am not asking for solution, I am asking why this cached version failed and a dp solution perhaps if possible. I think it's about algorithm only. And also there is a link to the original question for clarity. $\endgroup$ – Hearen Apr 17 '19 at 6:43
  • $\begingroup$ Dynamic programming is an implementation of caching. $\endgroup$ – Yuval Filmus Apr 21 '19 at 3:49
2
$\begingroup$

Why did it fail?

Look at the code cache = new int[size+1][volume+1];. Suppose size is 1 and volume is $10^9$. One int uses 4 bytes. So this cache will use $4 \times 2 \times 10^9$ bytes, which is about 8G, which is way much bigger than the limit, 32768K. So the online judge will show you out-of-memory error.

Could a DP solution without backtracking be found for this?

The right strategy here is called "meet in the middle". Here is the idea of the algorithm, where $w$ is the volume of the bag.

  1. Split the items into $A$ and $B$, two lists of approximately equal size.
  2. Compute all possible sums of items in A, appending them to array arrA. Sort arrA.
  3. Compute all possible sums of items in A, appending them to array arrB. Sort arrB.
  4. For each number in arrA, find the last element in arrB such that the sum of the two is not greater than $w$. Let its index be $upper$. Add $upper + 1$ to the total.
  5. Return total.

The time-complexity of the algorithm is $O(n2^{n/2})$, which comes from sorting two arrays of size about $2^{n/2}$. For $n= 30$, we get $30\times 2^{30/2}=30\times32768$, which is about 1 million.

The space-complexity of the algorithm is $O(2^{n/2})$. For example, if $n= 30$, we allocate two arrays of longs of size $2^{15}$, which spans $2\times2^{15}\times8$ bytes, which is less than 600K. We need some extra work memory for sorting and etc, which will at most triple the memory allocated specifically for our algorithm.

Here is the implementation in Java.

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        final int n = sc.nextInt();
        final int w = sc.nextInt();
        final long[] v = new long[n];
        for (int i = 0; i < n; ++i) v[i] = sc.nextLong();

        int total;
        if (n == 1) {
            if (v[0] <= w) total = 2;
            else total = 1;
        } else {
            final int half_n = n / 2;

            final long[] front = getSortedSums(v, 0, half_n);
            final long[] behind = getSortedSums(v, half_n, n);

            int lastIndexFront = front.length - 1;
            while (front[lastIndexFront] > w) lastIndexFront--;

            int upper = behind.length - 1;
            for (int i = 0; i <= lastIndexFront; i++) {
                while (front[i] + behind[upper] > w) upper--;
                total += upper + 1;
            }
        }

        System.out.println(total);
    }

    // Return all possible sums of elements in the specified segment of v,
    // sorted. Note the first sum is 0, representing the empty sum.
    private static long[] getSortedSums(long[] v, final int low, final int high) {
        int index = 0;
        final long[] sums = new long[1 << (high - low)];
        for (int i = low; i < high; i++) {
            long u = v[i];
            int end = 1 << (i - low);
            for (int j = 0; j < end; j++) {
                sums[++index] = sums[j] + u;
            }
        }
        Arrays.sort(sums);
        return sums;
    }
}
$\endgroup$
  • $\begingroup$ Thank you so much, I will check its details when I got back. Thank you, upvoted ;) first $\endgroup$ – Hearen Apr 19 '19 at 23:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.