import random
import unittest
from example import knapsack


class DPTests(unittest.TestCase):
    def test_no_reuse_and_boundaries(self):
        self.assertEqual(knapsack([(2, 3)], 4), 3)
        self.assertEqual(knapsack([], 5), 0)
        self.assertEqual(knapsack([(1, -2)], 3), 0)
        self.assertEqual(knapsack([(2, 3)], 0), 0)
        with self.assertRaises(ValueError):
            knapsack([(0, 3)], 4)

    def test_against_subsets(self):
        rng = random.Random(13)
        for _ in range(100):
            items = [(rng.randint(1, 5), rng.randint(-2, 9)) for _ in range(rng.randrange(8))]
            cap = rng.randrange(12)
            best = 0
            for mask in range(1 << len(items)):
                picked = [item for i, item in enumerate(items) if mask & (1 << i)]
                if sum(w for w, _ in picked) <= cap:
                    best = max(best, sum(v for _, v in picked))
            self.assertEqual(knapsack(items, cap), best)


if __name__ == '__main__':
    unittest.main()