0
$\begingroup$

How does one go about analyzing the running time of a naive recursive solution to the unbounded knapsack problem? Lots of sources say the naive implementation is "exponential" without giving more detail.

For reference, here's a bit of Python code that implements the brute-force solution. Note that this can run for a long time even on smallish inputs. One of the interesting things about Knapsack is some inputs are lot harder than others.

import random, time
import sys

class Item:
    def __init__(self, weight, value):
        self.weight = weight
        self.value = value

    def __repr__(self):
        return "Item(weight={}, value={})".format(self.weight, self.value)


def knapsack(capacity):
    if capacity==0: return ([], 0)
    max_value = 0
    max_contents = []
    for item in items:
        if item.weight <= capacity:
            (contents, value) = knapsack(capacity-item.weight)
            if value + item.value > max_value:
                max_value = value + item.value
                max_contents = [item]
                max_contents.extend(contents)
    return (max_contents, max_value)

def generate_items(n, max_weight, vwratio=1):
    items = []
    weights = random.sample(range(1,max_weight+1),n)
    for weight in weights:
        variation = weight/10
        value = max(1, int(vwratio*weight + random.gauss(-variation, variation)))
        item = Item(weight, value)
        items.append(item)
    return items

n=30
max_item_weight=100
capacity=100

items = generate_items(n=n, max_weight=max_item_weight, vwratio=1.1)

st = time.time()
solution, value = knapsack(capacity)
print("completed in %f"%(time.time() - st))

Note that this algorithm can be improved upon nicely by memoizing yielding a O(nW) pseudo-polynomial time solution, but I was interested in understanding how to analyze the brute-force algorithm more precisely.

$\endgroup$
  • 2
    $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – David Richerby Jul 9 '16 at 18:43
  • $\begingroup$ Thanks for the guidance. I suspect if I knew the exact concept I was looking for, I could find my answer. The crux of my question is about how to turn an intuition (if it's not totally wrong) into a solid argument about bounds on running time. For what it's worth, I'm not looking for a gimme on my homework - it's a couple decades too late for that. I dug out an old edition of Sedgewick and wanted a bit more explanation than is in the text. I'm happy to take suggestions on how to ask the question properly. If it's just a wrong-headed question, I'll delete it. $\endgroup$ – cbare Jul 9 '16 at 23:07
  • 2
    $\begingroup$ Welcome to Computer Science! Let me direct you towards our reference questions which cover your problem in detail. Please work through the related material listed there, try to solve your problem again and edit to include your attempts along with the specific problems you encountered. Good luck! $\endgroup$ – D.W. Jul 11 '16 at 6:12
  • 1
    $\begingroup$ Thanks, @D.W., for the links. Raphael's post on Translating Code to Mathematics is nicely written and this post on Recurrences might help in this particular case. People seem not to like my question. That's OK; no one's under any obligation. I'm going to leave it here, along with my attempt at an answer. If it helps anyone, great. If not, it's not hurting anything. $\endgroup$ – cbare Jul 12 '16 at 18:28
  • $\begingroup$ Welcome to Computer Science! Please get rid of the source code and replace it with ideas, pseudo code and arguments of correctness. See here and here for related meta discussions. $\endgroup$ – Raphael Jul 12 '16 at 21:44
1
$\begingroup$

You will be trying every sequence of items that fit, adding the same item multiple times if that is possible. So first you need to check if you actually wanted the same item to be used multiple times. Whether you did or not, you can make the algorithm a lot more efficient if you only add items in ascending order, that is if you added item k, then you only add further items k, k+1, k+2, ... or only items k+1, k+2, ... depending on whether you wanted to allow the same item multiple times.

You could also save substantial time again by sorting the items for example in descending order. If you do that, you can try adding items with the smallest first, and when an item doesn't fit, you know further items won't fit either - so you can stop the search there.

Anyway, the time depends entirely on the data. If all the items are in size between capacity/2 and capacity then it's $O (n^2)$ (could be $O (n)$ with improvements described earlier). If any item has weight 0, then your algorithm never ends; you should check that first. In the worst case where all n items have size 1 and the capacity is W, your algorithm takes $n^W$ steps - that's especially bad because that particular problem is trivial.

$\endgroup$
0
$\begingroup$

Here's my attempt to answer my own question, which may very well be wrong. Comments and alternatives welcome.

In each step, we consider n options for the next item to add to the pack, where n is the number of different types of items. The number of such steps we end up doing depends on W, the capacity of our knapsack (maximum weight it can hold). The exact relation between W and the depth of the recursion is a little mysterious, depending on the particular values. But, if we increase the capacity by some factor, we'll on average recurse one level deeper, leading me to guess that it's bounded by O(n^cW) for some constant c.

Alternatively, I could imagine trying to extend the 2^n bound of the 0-1 knapsack problem to the unbounded case. Something like 2^(nW) where the number of binary in/out decisions we have to make is proportional to both n and W.

$\endgroup$

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.