Solution to the 0/1 knapsack in PythonDynamic programming knapsack solutionKnapsack branch and bound: forward filterFunctional Knapsack Problem in PythonPython Knapsack problem using branch and bound algorithmPython Knapsack problem: greedyFractional KnapsackFractional Knapsack in JavaKnapsack algorithm in JavaScript - Integer weights and values0-1 Knapsack problem - implementationKnapsack problem with duplicate elements
What happens if you roll doubles 3 times then land on "Go to jail?"
Why didn't Theresa May consult with Parliament before negotiating a deal with the EU?
Applicability of Single Responsibility Principle
How to write papers efficiently when English isn't my first language?
How does Loki do this?
Hostile work environment after whistle-blowing on coworker and our boss. What do I do?
Short story about space worker geeks who zone out by 'listening' to radiation from stars
Sequence of Tenses: Translating the subjunctive
Pole-zeros of a real-valued causal FIR system
Is it appropriate to ask a job candidate if we can record their interview?
Lay out the Carpet
Did Dumbledore lie to Harry about how long he had James Potter's invisibility cloak when he was examining it? If so, why?
Where does the Z80 processor start executing from?
Is there a good way to store credentials outside of a password manager?
Two monoidal structures and copowering
How does buying out courses with grant money work?
Implement the Thanos sorting algorithm
Integer addition + constant, is it a group?
A Rare Riley Riddle
Failed to fetch jessie backports repository
Go Pregnant or Go Home
What is the intuitive meaning of having a linear relationship between the logs of two variables?
Class Action - which options I have?
How do I go from 300 unfinished/half written blog posts, to published posts?
Solution to the 0/1 knapsack in Python
Dynamic programming knapsack solutionKnapsack branch and bound: forward filterFunctional Knapsack Problem in PythonPython Knapsack problem using branch and bound algorithmPython Knapsack problem: greedyFractional KnapsackFractional Knapsack in JavaKnapsack algorithm in JavaScript - Integer weights and values0-1 Knapsack problem - implementationKnapsack problem with duplicate elements
$begingroup$
So I made a version for the 0/1 knapsack problem myself (using matrix dynamic programming algorithm). Given a list of items with name, value, and weight, my function computes correctly the optimal value with total weight <= allowed weight.
I don't know if my code is clean and pythonic enough, I would greatly appreciate it if you give me some comments, thanks.
def knapsack(W, items):
"""
Given a list of items with name, value and weight.
Return the optimal value with total weight <= allowed weight and
list of picked items.
"""
n = len(items)
k = [[0 for x in range(W+1)] for x in range(n+1)]
for i in range(n+1):
for w in range(W+1):
if i == 0 or w == 0:
k[i][w] = 0
elif items[i-1][2] <= w:
k[i][w] = max(items[i-1][1] + k[i-1][w-items[i-1][2]], k[i-1][w])
else:
k[i][w] = k[i-1][w]
picked = []
set_trace(k, n, W, items, picked)
return k[n][W], picked
# find which item are picked
def set_trace(k, n, W, items, picked):
for i in range(n, 0, -1):
if k[i][W] != k[i-1][W]:
picked.append(items[i-1])
set_trace(k, i-1, W-items[i-1][2], items, picked)
break
if __name__ == '__main__':
items = [('A', 1, 1), ('B', 4, 3), ('C', 5, 4), ('D', 7, 5)]
max_value, picked = knapsack(7, items)
print("Maximum value:", max_value)
print("Name", "Value", "Weight")
for item in reversed(picked):
print(item[0], ' '*2, item[1], ' '*3, item[2])
Output:
Maximum value: 9
Name Value Weight
B 4 3
C 5 4
python algorithm
$endgroup$
add a comment |
$begingroup$
So I made a version for the 0/1 knapsack problem myself (using matrix dynamic programming algorithm). Given a list of items with name, value, and weight, my function computes correctly the optimal value with total weight <= allowed weight.
I don't know if my code is clean and pythonic enough, I would greatly appreciate it if you give me some comments, thanks.
def knapsack(W, items):
"""
Given a list of items with name, value and weight.
Return the optimal value with total weight <= allowed weight and
list of picked items.
"""
n = len(items)
k = [[0 for x in range(W+1)] for x in range(n+1)]
for i in range(n+1):
for w in range(W+1):
if i == 0 or w == 0:
k[i][w] = 0
elif items[i-1][2] <= w:
k[i][w] = max(items[i-1][1] + k[i-1][w-items[i-1][2]], k[i-1][w])
else:
k[i][w] = k[i-1][w]
picked = []
set_trace(k, n, W, items, picked)
return k[n][W], picked
# find which item are picked
def set_trace(k, n, W, items, picked):
for i in range(n, 0, -1):
if k[i][W] != k[i-1][W]:
picked.append(items[i-1])
set_trace(k, i-1, W-items[i-1][2], items, picked)
break
if __name__ == '__main__':
items = [('A', 1, 1), ('B', 4, 3), ('C', 5, 4), ('D', 7, 5)]
max_value, picked = knapsack(7, items)
print("Maximum value:", max_value)
print("Name", "Value", "Weight")
for item in reversed(picked):
print(item[0], ' '*2, item[1], ' '*3, item[2])
Output:
Maximum value: 9
Name Value Weight
B 4 3
C 5 4
python algorithm
$endgroup$
add a comment |
$begingroup$
So I made a version for the 0/1 knapsack problem myself (using matrix dynamic programming algorithm). Given a list of items with name, value, and weight, my function computes correctly the optimal value with total weight <= allowed weight.
I don't know if my code is clean and pythonic enough, I would greatly appreciate it if you give me some comments, thanks.
def knapsack(W, items):
"""
Given a list of items with name, value and weight.
Return the optimal value with total weight <= allowed weight and
list of picked items.
"""
n = len(items)
k = [[0 for x in range(W+1)] for x in range(n+1)]
for i in range(n+1):
for w in range(W+1):
if i == 0 or w == 0:
k[i][w] = 0
elif items[i-1][2] <= w:
k[i][w] = max(items[i-1][1] + k[i-1][w-items[i-1][2]], k[i-1][w])
else:
k[i][w] = k[i-1][w]
picked = []
set_trace(k, n, W, items, picked)
return k[n][W], picked
# find which item are picked
def set_trace(k, n, W, items, picked):
for i in range(n, 0, -1):
if k[i][W] != k[i-1][W]:
picked.append(items[i-1])
set_trace(k, i-1, W-items[i-1][2], items, picked)
break
if __name__ == '__main__':
items = [('A', 1, 1), ('B', 4, 3), ('C', 5, 4), ('D', 7, 5)]
max_value, picked = knapsack(7, items)
print("Maximum value:", max_value)
print("Name", "Value", "Weight")
for item in reversed(picked):
print(item[0], ' '*2, item[1], ' '*3, item[2])
Output:
Maximum value: 9
Name Value Weight
B 4 3
C 5 4
python algorithm
$endgroup$
So I made a version for the 0/1 knapsack problem myself (using matrix dynamic programming algorithm). Given a list of items with name, value, and weight, my function computes correctly the optimal value with total weight <= allowed weight.
I don't know if my code is clean and pythonic enough, I would greatly appreciate it if you give me some comments, thanks.
def knapsack(W, items):
"""
Given a list of items with name, value and weight.
Return the optimal value with total weight <= allowed weight and
list of picked items.
"""
n = len(items)
k = [[0 for x in range(W+1)] for x in range(n+1)]
for i in range(n+1):
for w in range(W+1):
if i == 0 or w == 0:
k[i][w] = 0
elif items[i-1][2] <= w:
k[i][w] = max(items[i-1][1] + k[i-1][w-items[i-1][2]], k[i-1][w])
else:
k[i][w] = k[i-1][w]
picked = []
set_trace(k, n, W, items, picked)
return k[n][W], picked
# find which item are picked
def set_trace(k, n, W, items, picked):
for i in range(n, 0, -1):
if k[i][W] != k[i-1][W]:
picked.append(items[i-1])
set_trace(k, i-1, W-items[i-1][2], items, picked)
break
if __name__ == '__main__':
items = [('A', 1, 1), ('B', 4, 3), ('C', 5, 4), ('D', 7, 5)]
max_value, picked = knapsack(7, items)
print("Maximum value:", max_value)
print("Name", "Value", "Weight")
for item in reversed(picked):
print(item[0], ' '*2, item[1], ' '*3, item[2])
Output:
Maximum value: 9
Name Value Weight
B 4 3
C 5 4
python algorithm
python algorithm
edited Apr 11 '16 at 13:21
asked Apr 11 '16 at 12:04
user102577
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Kudos for using list comprehensions. However picked = []; set_trace(k, n, W, items, picked)
and picked.append(items[i-1])
doesn't feel as good.
One could expect set_trace
to build the list and return it. Even better, would be to picked = list(set_trace(k, n, W, items))
, meaning set_trace
would be a generator (with a pretty terrible name).
In order to do so, you first have to come to the conclusion that the recursion is really not necessary. All you do, in that recursive call, is continue the iteration at the next step with a different W
. And that's it, you break
. You could have just replace these two lines with W -= items[i-1][2]
. Doing so, you could replace the append
with a yield
and you have your generator:
def set_trace(k, n, W, items):
for i in range(n, 0, -1):
if k[i][W] != k[i-1][W]:
yield items[i-1]
W -= items[i-1][2]
this lets you define picked = list(set_trace(k, n, W, items))
.
However, n
is len(items)
so you might as well not pass it as a parameter and compute it at the beginning of the function.
You can also get much better readability by improving your naming. I understand that you named your variables based of the math theory that this problem relly on, but single letter variable names are a poor choice.
Same for using a simple tuple to store your items: it doesn't convey meaning. Use a namedtuple
instead.
Last thing, since you are skipping the first row and first column of k
, you can use slices and the enumerate
builtin to avoid using so much brackets; you can also improve set_trace
in such a way by using zip
to create pairwise values of potential weights:
from collections import namedtuple
Item = namedtuple('Item', 'name value weight')
def knapsack(allowed_weight, items):
"""
Given a list of items with name, value and weight.
Return the optimal value with total weight <= allowed weight and
list of picked items.
"""
k = [
[0 for x in range(allowed_weight + 1)]
for x in range(len(items) + 1)
]
for next_idx, (item, weights) in enumerate(zip(items, k), 1):
for w, current_weight in enumerate(weights[1:], 1):
if item.weight <= w:
k[next_idx][w] = max(
item.value + weights[w - item.weight],
current_weight
)
else:
k[next_idx][w] = current_weight
return k[-1][-1], list(fetch_items(k, allowed_weight, items))
# find which item are picked
def fetch_items(k, allowed_weight, items):
for item, weights_p, weights_n in zip(items[::-1], k[-2::-1], k[::-1]):
if weights_n[allowed_weight] != weights_p[allowed_weight]:
yield item
allowed_weight -= item.weight
if __name__ == '__main__':
items = [
Item('A', 1, 1),
Item('B', 4, 3),
Item('C', 5, 4),
Item('D', 7, 5),
]
max_value, picked = knapsack(7, items)
print("Maximum value:", max_value)
print("Name", "Value", "Weight")
for item in reversed(picked):
print(item.name, ' '*2, item.value, ' '*3, item.weight)
$endgroup$
add a comment |
$begingroup$
Python Code for 1-0 Knapsack is:-
import numpy as np
def Knapsack(W, wt, profit):
print('-------------------------------------------------------------')
print('Total Weight: %s' %W)
print('Weights: %s' %wt)
print('Profit: %s' %profit)
mat = np.zeros((len(wt)+1, W+1))
for i in range(0,len(wt)+1):
for w in range(0,W+1):
if i==0 or w==0:
mat[i][w] = 0
elif wt[i-1]>w:
mat[i][w] = mat[i-1][w]
else:
mat[i][w] = max(mat[i-1][w],(profit[i-1]+mat[i-1][w-wt[i-1]]))
k=W
list =[]
for i in range(len(wt),-1,-1):
if mat[i, k] != mat[i - 1, k]:
k = k - wt[i-1]
if i!=0:
list.append(i)
print('-------------------------------------------------------------')
print('Rows: items and columns: weight.')
print(mat)
#i have added this below code to transpose if wanted
#transpose = zip(*mat)
#for row in transpose:
# print(row)
print('-------------------------------------------------------------')
print('Maximum Profit: %s' %mat[len(wt)][W])
print('-------------------------------------------------------------')
print('Items Added')
print(list)
def main():
W = 5
Wt =[3,2,4,1]
Pt =[100,20,60,40]
Knapsack(W,Wt,Pt)
main()
OUTPUT:-
-------------------------------------------------------------
Total Weight: 5
Weights: [3, 2, 4, 1]
Profit: [100, 20, 60, 40]
-------------------------------------------------------------
Rows: items and columns: weight.
[[ 0. 0. 0. 0. 0. 0.]
[ 0. 0. 0. 100. 100. 100.]
[ 0. 0. 20. 100. 100. 120.]
[ 0. 0. 20. 100. 100. 120.]
[ 0. 40. 40. 100. 140. 140.]]
-------------------------------------------------------------
Maximum Profit: 140.0
-------------------------------------------------------------
Items Added
[4, 1]
New contributor
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
);
);
, "mathjax-editing");
StackExchange.ifUsing("editor", function ()
StackExchange.using("externalEditor", function ()
StackExchange.using("snippets", function ()
StackExchange.snippets.init();
);
);
, "code-snippets");
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "196"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
var $window = $(window),
onScroll = function(e)
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom))
StackExchange.using('gps', function() StackExchange.gps.track('embedded_signup_form.view', location: 'question_page' ); );
$window.unbind('scroll', onScroll);
;
$window.on('scroll', onScroll);
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f125374%2fsolution-to-the-0-1-knapsack-in-python%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Kudos for using list comprehensions. However picked = []; set_trace(k, n, W, items, picked)
and picked.append(items[i-1])
doesn't feel as good.
One could expect set_trace
to build the list and return it. Even better, would be to picked = list(set_trace(k, n, W, items))
, meaning set_trace
would be a generator (with a pretty terrible name).
In order to do so, you first have to come to the conclusion that the recursion is really not necessary. All you do, in that recursive call, is continue the iteration at the next step with a different W
. And that's it, you break
. You could have just replace these two lines with W -= items[i-1][2]
. Doing so, you could replace the append
with a yield
and you have your generator:
def set_trace(k, n, W, items):
for i in range(n, 0, -1):
if k[i][W] != k[i-1][W]:
yield items[i-1]
W -= items[i-1][2]
this lets you define picked = list(set_trace(k, n, W, items))
.
However, n
is len(items)
so you might as well not pass it as a parameter and compute it at the beginning of the function.
You can also get much better readability by improving your naming. I understand that you named your variables based of the math theory that this problem relly on, but single letter variable names are a poor choice.
Same for using a simple tuple to store your items: it doesn't convey meaning. Use a namedtuple
instead.
Last thing, since you are skipping the first row and first column of k
, you can use slices and the enumerate
builtin to avoid using so much brackets; you can also improve set_trace
in such a way by using zip
to create pairwise values of potential weights:
from collections import namedtuple
Item = namedtuple('Item', 'name value weight')
def knapsack(allowed_weight, items):
"""
Given a list of items with name, value and weight.
Return the optimal value with total weight <= allowed weight and
list of picked items.
"""
k = [
[0 for x in range(allowed_weight + 1)]
for x in range(len(items) + 1)
]
for next_idx, (item, weights) in enumerate(zip(items, k), 1):
for w, current_weight in enumerate(weights[1:], 1):
if item.weight <= w:
k[next_idx][w] = max(
item.value + weights[w - item.weight],
current_weight
)
else:
k[next_idx][w] = current_weight
return k[-1][-1], list(fetch_items(k, allowed_weight, items))
# find which item are picked
def fetch_items(k, allowed_weight, items):
for item, weights_p, weights_n in zip(items[::-1], k[-2::-1], k[::-1]):
if weights_n[allowed_weight] != weights_p[allowed_weight]:
yield item
allowed_weight -= item.weight
if __name__ == '__main__':
items = [
Item('A', 1, 1),
Item('B', 4, 3),
Item('C', 5, 4),
Item('D', 7, 5),
]
max_value, picked = knapsack(7, items)
print("Maximum value:", max_value)
print("Name", "Value", "Weight")
for item in reversed(picked):
print(item.name, ' '*2, item.value, ' '*3, item.weight)
$endgroup$
add a comment |
$begingroup$
Kudos for using list comprehensions. However picked = []; set_trace(k, n, W, items, picked)
and picked.append(items[i-1])
doesn't feel as good.
One could expect set_trace
to build the list and return it. Even better, would be to picked = list(set_trace(k, n, W, items))
, meaning set_trace
would be a generator (with a pretty terrible name).
In order to do so, you first have to come to the conclusion that the recursion is really not necessary. All you do, in that recursive call, is continue the iteration at the next step with a different W
. And that's it, you break
. You could have just replace these two lines with W -= items[i-1][2]
. Doing so, you could replace the append
with a yield
and you have your generator:
def set_trace(k, n, W, items):
for i in range(n, 0, -1):
if k[i][W] != k[i-1][W]:
yield items[i-1]
W -= items[i-1][2]
this lets you define picked = list(set_trace(k, n, W, items))
.
However, n
is len(items)
so you might as well not pass it as a parameter and compute it at the beginning of the function.
You can also get much better readability by improving your naming. I understand that you named your variables based of the math theory that this problem relly on, but single letter variable names are a poor choice.
Same for using a simple tuple to store your items: it doesn't convey meaning. Use a namedtuple
instead.
Last thing, since you are skipping the first row and first column of k
, you can use slices and the enumerate
builtin to avoid using so much brackets; you can also improve set_trace
in such a way by using zip
to create pairwise values of potential weights:
from collections import namedtuple
Item = namedtuple('Item', 'name value weight')
def knapsack(allowed_weight, items):
"""
Given a list of items with name, value and weight.
Return the optimal value with total weight <= allowed weight and
list of picked items.
"""
k = [
[0 for x in range(allowed_weight + 1)]
for x in range(len(items) + 1)
]
for next_idx, (item, weights) in enumerate(zip(items, k), 1):
for w, current_weight in enumerate(weights[1:], 1):
if item.weight <= w:
k[next_idx][w] = max(
item.value + weights[w - item.weight],
current_weight
)
else:
k[next_idx][w] = current_weight
return k[-1][-1], list(fetch_items(k, allowed_weight, items))
# find which item are picked
def fetch_items(k, allowed_weight, items):
for item, weights_p, weights_n in zip(items[::-1], k[-2::-1], k[::-1]):
if weights_n[allowed_weight] != weights_p[allowed_weight]:
yield item
allowed_weight -= item.weight
if __name__ == '__main__':
items = [
Item('A', 1, 1),
Item('B', 4, 3),
Item('C', 5, 4),
Item('D', 7, 5),
]
max_value, picked = knapsack(7, items)
print("Maximum value:", max_value)
print("Name", "Value", "Weight")
for item in reversed(picked):
print(item.name, ' '*2, item.value, ' '*3, item.weight)
$endgroup$
add a comment |
$begingroup$
Kudos for using list comprehensions. However picked = []; set_trace(k, n, W, items, picked)
and picked.append(items[i-1])
doesn't feel as good.
One could expect set_trace
to build the list and return it. Even better, would be to picked = list(set_trace(k, n, W, items))
, meaning set_trace
would be a generator (with a pretty terrible name).
In order to do so, you first have to come to the conclusion that the recursion is really not necessary. All you do, in that recursive call, is continue the iteration at the next step with a different W
. And that's it, you break
. You could have just replace these two lines with W -= items[i-1][2]
. Doing so, you could replace the append
with a yield
and you have your generator:
def set_trace(k, n, W, items):
for i in range(n, 0, -1):
if k[i][W] != k[i-1][W]:
yield items[i-1]
W -= items[i-1][2]
this lets you define picked = list(set_trace(k, n, W, items))
.
However, n
is len(items)
so you might as well not pass it as a parameter and compute it at the beginning of the function.
You can also get much better readability by improving your naming. I understand that you named your variables based of the math theory that this problem relly on, but single letter variable names are a poor choice.
Same for using a simple tuple to store your items: it doesn't convey meaning. Use a namedtuple
instead.
Last thing, since you are skipping the first row and first column of k
, you can use slices and the enumerate
builtin to avoid using so much brackets; you can also improve set_trace
in such a way by using zip
to create pairwise values of potential weights:
from collections import namedtuple
Item = namedtuple('Item', 'name value weight')
def knapsack(allowed_weight, items):
"""
Given a list of items with name, value and weight.
Return the optimal value with total weight <= allowed weight and
list of picked items.
"""
k = [
[0 for x in range(allowed_weight + 1)]
for x in range(len(items) + 1)
]
for next_idx, (item, weights) in enumerate(zip(items, k), 1):
for w, current_weight in enumerate(weights[1:], 1):
if item.weight <= w:
k[next_idx][w] = max(
item.value + weights[w - item.weight],
current_weight
)
else:
k[next_idx][w] = current_weight
return k[-1][-1], list(fetch_items(k, allowed_weight, items))
# find which item are picked
def fetch_items(k, allowed_weight, items):
for item, weights_p, weights_n in zip(items[::-1], k[-2::-1], k[::-1]):
if weights_n[allowed_weight] != weights_p[allowed_weight]:
yield item
allowed_weight -= item.weight
if __name__ == '__main__':
items = [
Item('A', 1, 1),
Item('B', 4, 3),
Item('C', 5, 4),
Item('D', 7, 5),
]
max_value, picked = knapsack(7, items)
print("Maximum value:", max_value)
print("Name", "Value", "Weight")
for item in reversed(picked):
print(item.name, ' '*2, item.value, ' '*3, item.weight)
$endgroup$
Kudos for using list comprehensions. However picked = []; set_trace(k, n, W, items, picked)
and picked.append(items[i-1])
doesn't feel as good.
One could expect set_trace
to build the list and return it. Even better, would be to picked = list(set_trace(k, n, W, items))
, meaning set_trace
would be a generator (with a pretty terrible name).
In order to do so, you first have to come to the conclusion that the recursion is really not necessary. All you do, in that recursive call, is continue the iteration at the next step with a different W
. And that's it, you break
. You could have just replace these two lines with W -= items[i-1][2]
. Doing so, you could replace the append
with a yield
and you have your generator:
def set_trace(k, n, W, items):
for i in range(n, 0, -1):
if k[i][W] != k[i-1][W]:
yield items[i-1]
W -= items[i-1][2]
this lets you define picked = list(set_trace(k, n, W, items))
.
However, n
is len(items)
so you might as well not pass it as a parameter and compute it at the beginning of the function.
You can also get much better readability by improving your naming. I understand that you named your variables based of the math theory that this problem relly on, but single letter variable names are a poor choice.
Same for using a simple tuple to store your items: it doesn't convey meaning. Use a namedtuple
instead.
Last thing, since you are skipping the first row and first column of k
, you can use slices and the enumerate
builtin to avoid using so much brackets; you can also improve set_trace
in such a way by using zip
to create pairwise values of potential weights:
from collections import namedtuple
Item = namedtuple('Item', 'name value weight')
def knapsack(allowed_weight, items):
"""
Given a list of items with name, value and weight.
Return the optimal value with total weight <= allowed weight and
list of picked items.
"""
k = [
[0 for x in range(allowed_weight + 1)]
for x in range(len(items) + 1)
]
for next_idx, (item, weights) in enumerate(zip(items, k), 1):
for w, current_weight in enumerate(weights[1:], 1):
if item.weight <= w:
k[next_idx][w] = max(
item.value + weights[w - item.weight],
current_weight
)
else:
k[next_idx][w] = current_weight
return k[-1][-1], list(fetch_items(k, allowed_weight, items))
# find which item are picked
def fetch_items(k, allowed_weight, items):
for item, weights_p, weights_n in zip(items[::-1], k[-2::-1], k[::-1]):
if weights_n[allowed_weight] != weights_p[allowed_weight]:
yield item
allowed_weight -= item.weight
if __name__ == '__main__':
items = [
Item('A', 1, 1),
Item('B', 4, 3),
Item('C', 5, 4),
Item('D', 7, 5),
]
max_value, picked = knapsack(7, items)
print("Maximum value:", max_value)
print("Name", "Value", "Weight")
for item in reversed(picked):
print(item.name, ' '*2, item.value, ' '*3, item.weight)
answered Apr 11 '16 at 15:01
Mathias EttingerMathias Ettinger
25.1k33185
25.1k33185
add a comment |
add a comment |
$begingroup$
Python Code for 1-0 Knapsack is:-
import numpy as np
def Knapsack(W, wt, profit):
print('-------------------------------------------------------------')
print('Total Weight: %s' %W)
print('Weights: %s' %wt)
print('Profit: %s' %profit)
mat = np.zeros((len(wt)+1, W+1))
for i in range(0,len(wt)+1):
for w in range(0,W+1):
if i==0 or w==0:
mat[i][w] = 0
elif wt[i-1]>w:
mat[i][w] = mat[i-1][w]
else:
mat[i][w] = max(mat[i-1][w],(profit[i-1]+mat[i-1][w-wt[i-1]]))
k=W
list =[]
for i in range(len(wt),-1,-1):
if mat[i, k] != mat[i - 1, k]:
k = k - wt[i-1]
if i!=0:
list.append(i)
print('-------------------------------------------------------------')
print('Rows: items and columns: weight.')
print(mat)
#i have added this below code to transpose if wanted
#transpose = zip(*mat)
#for row in transpose:
# print(row)
print('-------------------------------------------------------------')
print('Maximum Profit: %s' %mat[len(wt)][W])
print('-------------------------------------------------------------')
print('Items Added')
print(list)
def main():
W = 5
Wt =[3,2,4,1]
Pt =[100,20,60,40]
Knapsack(W,Wt,Pt)
main()
OUTPUT:-
-------------------------------------------------------------
Total Weight: 5
Weights: [3, 2, 4, 1]
Profit: [100, 20, 60, 40]
-------------------------------------------------------------
Rows: items and columns: weight.
[[ 0. 0. 0. 0. 0. 0.]
[ 0. 0. 0. 100. 100. 100.]
[ 0. 0. 20. 100. 100. 120.]
[ 0. 0. 20. 100. 100. 120.]
[ 0. 40. 40. 100. 140. 140.]]
-------------------------------------------------------------
Maximum Profit: 140.0
-------------------------------------------------------------
Items Added
[4, 1]
New contributor
$endgroup$
add a comment |
$begingroup$
Python Code for 1-0 Knapsack is:-
import numpy as np
def Knapsack(W, wt, profit):
print('-------------------------------------------------------------')
print('Total Weight: %s' %W)
print('Weights: %s' %wt)
print('Profit: %s' %profit)
mat = np.zeros((len(wt)+1, W+1))
for i in range(0,len(wt)+1):
for w in range(0,W+1):
if i==0 or w==0:
mat[i][w] = 0
elif wt[i-1]>w:
mat[i][w] = mat[i-1][w]
else:
mat[i][w] = max(mat[i-1][w],(profit[i-1]+mat[i-1][w-wt[i-1]]))
k=W
list =[]
for i in range(len(wt),-1,-1):
if mat[i, k] != mat[i - 1, k]:
k = k - wt[i-1]
if i!=0:
list.append(i)
print('-------------------------------------------------------------')
print('Rows: items and columns: weight.')
print(mat)
#i have added this below code to transpose if wanted
#transpose = zip(*mat)
#for row in transpose:
# print(row)
print('-------------------------------------------------------------')
print('Maximum Profit: %s' %mat[len(wt)][W])
print('-------------------------------------------------------------')
print('Items Added')
print(list)
def main():
W = 5
Wt =[3,2,4,1]
Pt =[100,20,60,40]
Knapsack(W,Wt,Pt)
main()
OUTPUT:-
-------------------------------------------------------------
Total Weight: 5
Weights: [3, 2, 4, 1]
Profit: [100, 20, 60, 40]
-------------------------------------------------------------
Rows: items and columns: weight.
[[ 0. 0. 0. 0. 0. 0.]
[ 0. 0. 0. 100. 100. 100.]
[ 0. 0. 20. 100. 100. 120.]
[ 0. 0. 20. 100. 100. 120.]
[ 0. 40. 40. 100. 140. 140.]]
-------------------------------------------------------------
Maximum Profit: 140.0
-------------------------------------------------------------
Items Added
[4, 1]
New contributor
$endgroup$
add a comment |
$begingroup$
Python Code for 1-0 Knapsack is:-
import numpy as np
def Knapsack(W, wt, profit):
print('-------------------------------------------------------------')
print('Total Weight: %s' %W)
print('Weights: %s' %wt)
print('Profit: %s' %profit)
mat = np.zeros((len(wt)+1, W+1))
for i in range(0,len(wt)+1):
for w in range(0,W+1):
if i==0 or w==0:
mat[i][w] = 0
elif wt[i-1]>w:
mat[i][w] = mat[i-1][w]
else:
mat[i][w] = max(mat[i-1][w],(profit[i-1]+mat[i-1][w-wt[i-1]]))
k=W
list =[]
for i in range(len(wt),-1,-1):
if mat[i, k] != mat[i - 1, k]:
k = k - wt[i-1]
if i!=0:
list.append(i)
print('-------------------------------------------------------------')
print('Rows: items and columns: weight.')
print(mat)
#i have added this below code to transpose if wanted
#transpose = zip(*mat)
#for row in transpose:
# print(row)
print('-------------------------------------------------------------')
print('Maximum Profit: %s' %mat[len(wt)][W])
print('-------------------------------------------------------------')
print('Items Added')
print(list)
def main():
W = 5
Wt =[3,2,4,1]
Pt =[100,20,60,40]
Knapsack(W,Wt,Pt)
main()
OUTPUT:-
-------------------------------------------------------------
Total Weight: 5
Weights: [3, 2, 4, 1]
Profit: [100, 20, 60, 40]
-------------------------------------------------------------
Rows: items and columns: weight.
[[ 0. 0. 0. 0. 0. 0.]
[ 0. 0. 0. 100. 100. 100.]
[ 0. 0. 20. 100. 100. 120.]
[ 0. 0. 20. 100. 100. 120.]
[ 0. 40. 40. 100. 140. 140.]]
-------------------------------------------------------------
Maximum Profit: 140.0
-------------------------------------------------------------
Items Added
[4, 1]
New contributor
$endgroup$
Python Code for 1-0 Knapsack is:-
import numpy as np
def Knapsack(W, wt, profit):
print('-------------------------------------------------------------')
print('Total Weight: %s' %W)
print('Weights: %s' %wt)
print('Profit: %s' %profit)
mat = np.zeros((len(wt)+1, W+1))
for i in range(0,len(wt)+1):
for w in range(0,W+1):
if i==0 or w==0:
mat[i][w] = 0
elif wt[i-1]>w:
mat[i][w] = mat[i-1][w]
else:
mat[i][w] = max(mat[i-1][w],(profit[i-1]+mat[i-1][w-wt[i-1]]))
k=W
list =[]
for i in range(len(wt),-1,-1):
if mat[i, k] != mat[i - 1, k]:
k = k - wt[i-1]
if i!=0:
list.append(i)
print('-------------------------------------------------------------')
print('Rows: items and columns: weight.')
print(mat)
#i have added this below code to transpose if wanted
#transpose = zip(*mat)
#for row in transpose:
# print(row)
print('-------------------------------------------------------------')
print('Maximum Profit: %s' %mat[len(wt)][W])
print('-------------------------------------------------------------')
print('Items Added')
print(list)
def main():
W = 5
Wt =[3,2,4,1]
Pt =[100,20,60,40]
Knapsack(W,Wt,Pt)
main()
OUTPUT:-
-------------------------------------------------------------
Total Weight: 5
Weights: [3, 2, 4, 1]
Profit: [100, 20, 60, 40]
-------------------------------------------------------------
Rows: items and columns: weight.
[[ 0. 0. 0. 0. 0. 0.]
[ 0. 0. 0. 100. 100. 100.]
[ 0. 0. 20. 100. 100. 120.]
[ 0. 0. 20. 100. 100. 120.]
[ 0. 40. 40. 100. 140. 140.]]
-------------------------------------------------------------
Maximum Profit: 140.0
-------------------------------------------------------------
Items Added
[4, 1]
New contributor
New contributor
answered 18 mins ago
Abhishikt KadamAbhishikt Kadam
1
1
New contributor
New contributor
add a comment |
add a comment |
Thanks for contributing an answer to Code Review Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
var $window = $(window),
onScroll = function(e)
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom))
StackExchange.using('gps', function() StackExchange.gps.track('embedded_signup_form.view', location: 'question_page' ); );
$window.unbind('scroll', onScroll);
;
$window.on('scroll', onScroll);
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f125374%2fsolution-to-the-0-1-knapsack-in-python%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
var $window = $(window),
onScroll = function(e)
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom))
StackExchange.using('gps', function() StackExchange.gps.track('embedded_signup_form.view', location: 'question_page' ); );
$window.unbind('scroll', onScroll);
;
$window.on('scroll', onScroll);
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
var $window = $(window),
onScroll = function(e)
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom))
StackExchange.using('gps', function() StackExchange.gps.track('embedded_signup_form.view', location: 'question_page' ); );
$window.unbind('scroll', onScroll);
;
$window.on('scroll', onScroll);
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
var $window = $(window),
onScroll = function(e)
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom))
StackExchange.using('gps', function() StackExchange.gps.track('embedded_signup_form.view', location: 'question_page' ); );
$window.unbind('scroll', onScroll);
;
$window.on('scroll', onScroll);
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown