# Is this an optimal implementation for the knapsack algorithm?

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.

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):


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) == []


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. :)

• 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. Apr 5, 2020 at 15:59
• I tasted again and already found a bug 😁, I'm working on it Apr 5, 2020 at 16:21
• @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. Apr 5, 2020 at 17:46