diff options
author | William Carroll <wpcarro@gmail.com> | 2020-01-29T14·43+0000 |
---|---|---|
committer | William Carroll <wpcarro@gmail.com> | 2020-01-29T14·43+0000 |
commit | 5c9079a41059e077f2b71b68eb83ff9fcb2e38d1 (patch) | |
tree | dce7e3566b04213228fb3c92fc593ca18841d972 /data_structures_and_algorithms/knapsack-0-1.py | |
parent | fb9380ba268b3cd27372acadb87b14cc96163374 (diff) |
Splice ./universe directory into ./
Manually merging: - README.md: I added the description from universe/README.md into the heading of dotfiles/README.md. - .envrc: dotfiles/.envrc was a superset of universe/.envrc - .gitignore: Adding some of the ignored patterns from universe/.gitignore to dotfiles/.gitignore Everything else here should be a simple rename.
Diffstat (limited to 'data_structures_and_algorithms/knapsack-0-1.py')
-rw-r--r-- | data_structures_and_algorithms/knapsack-0-1.py | 38 |
1 files changed, 38 insertions, 0 deletions
diff --git a/data_structures_and_algorithms/knapsack-0-1.py b/data_structures_and_algorithms/knapsack-0-1.py new file mode 100644 index 000000000000..c72d19d4ed73 --- /dev/null +++ b/data_structures_and_algorithms/knapsack-0-1.py @@ -0,0 +1,38 @@ +import unittest +from math import floor + + +def knapify(xs, capacity=None): + assert capacity is not None + n = len(xs) + # For 0/1 Knapsack, we must use a table, since this will encode which values + # work for which items. This is cleaner than including a separate data + # structure to capture it. + maxes = [[0 for x in range(capacity + 1)] for x in range(n + 1)] + + # Build table maxes[][] in bottom up manner + for row in range(n + 1): + for col in range(capacity + 1): + if row == 0 or col == 0: + maxes[row][col] = 0 + elif xs[row - 1][0] <= col: + maxes[row][col] = max( + xs[row - 1][1] + maxes[row - 1][col - xs[row - 1][0]], + maxes[row - 1][col]) + else: + maxes[row][col] = maxes[row - 1][col] + + return maxes[-1][capacity] + + +################################################################################ +# Tests +################################################################################ +class Test(unittest.TestCase): + def test_one_cake(self): + actual = knapify([(3, 10), (2, 15), (7, 2), (12, 20)], capacity=12) + expected = None + self.assertEqual(actual, expected) + + +unittest.main(verbosity=2) |