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