Skip to content

Instantly share code, notes, and snippets.

@frydaykg

frydaykg/gist:7283974

Created November 2, 2013 22:00
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save frydaykg/7283974 to your computer and use it in GitHub Desktop.
Save frydaykg/7283974 to your computer and use it in GitHub Desktop.
Download ZIP
Knapsack problem #3
Raw
gistfile1.py
def solve(k, a):
b = set()
b.add(0)
b.add(a[0])
for i in range(1, len(a)):
tmp = set()
for j in b:
tmp.add(j)
if j + a[i] <= k:
tmp.add(j + a[i])
b = tmp
return k in b
a = [2, 43, 6546457, 4, 5, 7, 34, 1]
k = 15
print solve(k, a)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment