# Running time of naive recursive implementation of unbounded knapsack problem

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.

• 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. – David Richerby Jul 9 '16 at 18:43
• 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. – cbare Jul 9 '16 at 23:07
• 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! – D.W. Jul 11 '16 at 6:12
• 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. – cbare Jul 12 '16 at 18:28
• 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. – Raphael Jul 12 '16 at 21:44

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.