Brute force method to solve the 0-1 knapsack problem

Question

I know that the brute force method is not the best way to solve the 0-1 knapsack problem. I'm not quite getting the dynamic programming idea, but would like to know the following:

• If the brute force method can solve the problem with 20 items in 1 second - how many items can it solve in one day (2^16 s)?

I know that the time complexity of brute force is big O(2^n). But still I don't see how I can solve this.

Answer 1

As O(2^n) says adding one item will double computation time, giving the fact that one day equals 2^16 seconds, you more or less answered the question yourself.

A method solving a problem with 20 items in 1 second will will solve a problem with 20 + 16 = 36 items in a day.

Wow, downvote for the right answer, that's nice! So let us elaborate on this:

Calculation 1

As we know worst-case runtime for 20 items is 1 second, there is no need to experiment and guess the constant factor (c) as suggested in another answer.

Instead we can get it by simple calculation:

1 second = c * 2^20 => c = 1/2^20 = 2^-20

The equation we still have to solve, to find out, with how many items we can expect an answer in a day is:

1 day =~ 2^16 seconds = c * 2^n = 2^-20 * 2^n

multiplied by 2^20 on both sides we end up with:

2^36 = 2^n

Which we might logarithmize on both sides, if we don't see, that n=36 directly.

qed.

Calculation 2

After verification of the answer 36, let's take a closer look at the alternative suggested - experimenting with 40 and 80 items*.

[*: at least before the author changed from these numbers to n_1 and n_2]

Expermient 1 - 40 items

For 40 items the algorith will take 2^20 times the time it takes for 20 items, and as such:

2^20 = 1048576 s = 17476 min = 291 h = 12 days

While waiting those 12 days for our calculation to complete, let's take a look at our second suggestion.

Expermient 2 - 80 items

For 80 items we will have to deal with 2^60 times the time it takes for 20 items:

2^60 = 1152921504606846976 s = 19215358410114116 min = 320255973501901 h = 13343998895912 days = 36558901084 years

As scientists estimate the age of our universe to be something around 13.7 * 10^9 years our result of something like 36.5 * 10^9 years seems to be rather ambitious.

Good luck waiting anyways.

naive c * 2^n Algorithm

There were doubts wether such an algorithm exists, so here a sample brute-force algorithm working in c * 2^n.

Written in pseudo code, so familarity with a specific programming language should not be required.

# let w[1], ... , w[n] be the weights of the items
# let v[1], ... , v[n] be the values of the items
# let maxWeight be the capacity of the knapsack

bestValue := 0

function solve(n, currentWeight, currentValue) {

    if n = 0 and currentWeight <= maxWeight and currentValue > bestValue:
        bestValue := currentValue

    if n = 0: return

    # don't pack this item
    solve(n-1, currentWeight, currentValue)
    # pack this item
    solve(n-1, currentWeight + w[n], currentValue + v[n])
}

solve(n, 0, 0)

print bestValue

Assignments and comporisons made in solve all run in O(1).

Recursion depth is n with 2 recursive calls in each run, resulting in 2^n runs total.

Runtime is thus not only bound by O(2^n), but also of the form c*2^n as requested.

qed.

Answering still open questions

... taken from the comments section

1) How do you check a solution candidate in O(1) time? 2) Even the most naive algorithm may find a witness early and abort. 3) How do you make the jump from some abstract, unspecified combinatoric measure to runtime (in seconds)?

ad 1: O(1) time candidate check in the pseudo code example takes place in line 9:

if n = 0 and currentWeight >= maxWeight and currentValue > bestValue: bestValue := currentValue

ad 2: It indeed may

... if you are lucky or at least not very unlucky. Nevertheless there is no guarantee.

ad 3: The "jump" to computation time in seconds takes into account the trustworthyness of the information that

the brute force method can solve the problem with 20 items in 1 second

... (on a specific machine) given in the exercise, reading "the problem" as a synonym for the 0-1 knapsack problem, which, at least as I read it, should include all problem instances, even the ones taking worst-case time.

Answer 2

You can't. Landau notation does not hold enough information.

• You don't know the constant factor(s).
• With only $O$, you don't have a lower bound.
• It's only a worst-case bound; different runs with the number of items can have wildly different runtimes.
• Such bounds only hold in the limit, that is even $\leq c \cdot 2^n$ may not hold for those $n$ you can realistically run the algorithm for.

• The quantity bounded is not runtime but some abstract measure.

  In particular, effects like operation reordering, memory hierarchy and branch mispredictions routinely skrew with runtimes.

The best you can do is assume that the runtime behaves like $\approx c \cdot 2^n$, run experiments with $n_1$ and $n_2$ items and estimate the constant factor -- then it's simple rule of three. But given all the caveats listed above, the prediction is unlikely to be worth much.

Answer 3

There are two problems if the only things you know are "the time is O (2^n)" and "the problem is solved in 1 second for n = 20": One, big-O only gives you information for large n. You don't know what's large. You might have a problem that can be solved in exactly 1 second for any n ≤ 1 billion, and $2^{n-1,000,000,000}$ seconds for any larger n. Two, big-O gives an upper bound. Your time could be n/20 seconds for every n; n/20 is in O(2^n) but you can solve quite large problems in a day.

You can make a more or less educated guess that the execution time is $c * 2^n$ seconds for some unknown c, then you can calculate that $c = 2^{-20}$ and that 36 items give you an execution time of $2^{16}$ seconds. But that is a calculation based on a guess, and you need to be aware of that. You would want more than one data point to see how good your guess about the execution time is.