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