Is this an optimal implementation for the knapsack algorithm?

Question

I have implemented a solution for the knapsack problem while breaking an item is allowed. I've used the dictionary data structure where I used weight as a key and value per weight as a value. After that, I sorted the dictionary by value and filled the knapsack until there's no space left.

Here is my python code -

def calculateKnapsack():
 userinputNW = list(map(int, input().split()))
 n = userinputNW[0]
 weight = userinputNW[1]
 weightvaluedict = {}
 revenue = 0
 for x in range(n):
 vw = list(map(int, input().split()))
 weightvaluedict[vw[1]] = vw[0]/vw[1]
 weightvaluedict = {k: v for k, v in sorted(
 weightvaluedict.items(), key=lambda item: item[1], reverse=True)}
 for k, v in weightvaluedict.items():
 if weight == 0:
 break
 if k < weight:
 revenue += k * v
 weight -= k
 else:
 revenue += weight * v
 weight = 0
 return revenue

I'm confused if it is an optimal solution or not. I searched online and most of the tutorial used 2D array. I wanted to ensure my code's optimality. Suggestions are welcome.

Thanks. And also this is my first question on the Code review platform so please forgive me if I did anything wrong.

Answer 1

I don't understand what you mean by "the knapsack problem white fraction is allowed," not even if I assume that the word "white" should have been "while" or "what" or "where". The whole thing that makes the knapsack problem NP-hard is that you're not allowed to break up a single item into "fractions." So to understand what you meant, I tried to look at the code.

The first thing I do to understand a piece of code is, I look at its function signature. What arguments does the function take? What verbs and prepositions are used in its name? Consider:

def countPrimesUpTo(n):
def listPrimesUpTo(n):
def printPrimesLessThan(n):

Here's your function signature.

def calculateKnapsack():

Well, that didn't give me any information at all...!

The second way I try to understand a piece of code is to look at what it does; that is, look at its unit-tests.

assert listPrimesUpTo(10) == [2,3,5,7]
assert listPrimesUpTo(5) == [5]
assert listPrimesUpTo(1) == []

Here's your unit tests.

pass

Okay, I guess I should just give up on understanding what the code is intended to do, and focus on the code itself.

 userinputNW = list(map(int, input().split()))
 n = userinputNW[0]
 weight = userinputNW[1]

Oh hey! Here's something that looks like function arguments. You could immediately refactor your function into

def computeKnapsack(n, weight):

But then I go on and I see there's more input happening later...

 weightvaluedict = {}
 for x in range(n):
 vw = list(map(int, input().split()))
 weightvaluedict[vw[1]] = vw[0]/vw[1]
 weightvaluedict = {k: v for k, v in sorted(
 weightvaluedict.items(), key=lambda item: item[1], reverse=True)}

So now our knapsack function looks like

def computeKnapsackRevenue(weights, capacity):
 revenue = 0
 for size, value in weights.items():
 if capacity == 0:
 break
 if size < capacity:
 revenue += size * value
 capacity -= size
 else:
 revenue += capacity * value
 capacity = 0
 return revenue

and we have some boilerplate user-input code that looks like

 num_items, capacity = map(int, input().split())
 weights = {}
 for x in range(num_items):
 v, k = map(int, input().split())
 weights[k] = v / k
 weights = {k: v for k, v in sorted(
 weights.items(), key=lambda kv: kv[1], reverse=True)}

That last line isn't doing anything at all. It doesn't matter how you permute the list of items, if all you're doing with the result is stuffing it back into an unsorted dict. So we can erase that line.

 num_items, capacity = map(int, input().split())
 weights = {}
 for x in range(num_items):
 v, k = map(int, input().split())
 weights[k] = v / k
 revenue = computeKnapsackRevenue(weights, capacity)
 print(revenue)

And there's our program! We might add some unit tests to prove that it does what we expect:

 assert computeKnapsackRevenue({10: 8, 10: 9, 10: 10}, 0) == 0
 assert computeKnapsackRevenue({10: 8, 10: 9, 10: 10}, 20) == 190
 assert computeKnapsackRevenue({10: 8, 10: 9, 10: 10}, 25) == 230
 assert computeKnapsackRevenue({10: 8, 10: 9, 10: 10}, 30) == 270
 assert computeKnapsackRevenue({10: 8, 10: 9, 10: 10}, 40) == 270
 assert computeKnapsackRevenue({}, 40) == 0

We might even find that it has a bug. :)

• Mahmudul Hasan: The problem is exactly written like this - "A thief finds much more loot than his bag can fit. Help him to find the most valuable combination of items assuming that any fraction of a loot item can be put into his bag." I misspelled the word while.
• Mahmudul Hasan: I tasted again and already found a bug 😁, I'm working on it
• Quuxplusone: @MahmudulHasan: For future reference, it would have been a good idea to put that problem statement ("A thief finds...") at the top of your question.