Skip to content

Instantly share code, notes, and snippets.

@felipecruz

felipecruz/gist:1bb22a5ed49187a1630ab100a3420877

Last active November 23, 2016 15: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 felipecruz/1bb22a5ed49187a1630ab100a3420877 to your computer and use it in GitHub Desktop.
Save felipecruz/1bb22a5ed49187a1630ab100a3420877 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
gistfile1.txt
// Input:
// Values (stored in array v)
// Weights (stored in array w)
// Number of distinct items (n)
// Knapsack capacity (W)
for j from 0 to W do:
m[0, j] := 0
for i from 1 to n do:
for j from 0 to W do:
if w[i] > j then:
m[i, j] := m[i-1, j]
else:
m[i, j] := max(m[i-1, j], m[i-1, j-w[i]] + v[i])
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment