3
\$\begingroup\$

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.

\$\endgroup\$

1 Answer 1

2
\$\begingroup\$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.