0/1 Knapsack

Data Structures and Algorithms

Statement

Let there be n items whose weights and values are known, and a knapsack to carry the items. The knapsack cannot carry more than a certain weight capacity. Find the maximum total value fo items in the knapsack, usch that the total weight of items in the knapsack doesn’t exceed the capacity. If there’s no combination of weights that don’t exceed the capacity, then return 0.

An item cannot be broken up to fit in the knapsack, it’s either chosen or not chosen. An item cannot be added to the knapsack more than once.

Constraints

• 1 ≤ capacity ≤ 1000
• 1 ≤ values.length() ≤ 500
• weights.length() = values.length()
• 1 ≤ values[i] ≤ 1000
• 1 ≤ weights[i] ≤ capacity

Solution

"""
production algorithm
"""


class Solution:
    def max_profit(self, capacity, weights, values):
        """
        time complexity O(nc)
        space complexity O(nc)
        """
        n = len(weights)
        memo = [[0 if m == 0 or c == 0 else None for c in range(
            capacity + 1)] for m in range(n + 1)]

        for m in range(1, n + 1):
            for c in range(1, capacity + 1):
                if weights[m - 1] <= c:
                    memo[m][c] = max(
                        values[m - 1] + memo[m - 1][c - weights[m - 1]],
                        memo[m - 1][c])
                else:
                    memo[m][c] = memo[m - 1][c]

        return memo[n][capacity]

"""
unit tests
"""

from unittest import TestCase
from algorithms.dynamic_programming.knapsack_01.solution import Solution


class SolutionTestCase(TestCase):
    def test_01_knapskack(self):
        # Given
        capacity = 150
        weights = [15, 26, 38, 49, 54, 68]
        values = [24, 37, 43, 58, 67, 74]
        solution = Solution()

        # When
        actual = solution.max_profit(capacity, weights, values)

        # Then
        expected = 186
        self.assertEqual(actual, expected)

Strategy

Dynamic Programming.

Explanation

A 2-D matrix, whose dimensions are the capacity and number of items, is maintained to hold the optimal solution to the problem for capacity and number of items seen so far. In the trivial case, where the capacity or number of items is zero, the optimal solution is 0. Then, iteration of the capacity and number of items occurs. The optimal solution for smaller capacity and number of items is used to find the optimal solution for larger capacity and number of items. Iteration ends when the optimal solution has been found for the input capacity and number of items.

Notice, that the problem has optimal substructure, i.e. the optimal solution of larger capacity and number of items can be found from the optimal solution of smaller capacity and number of items. Also notice, that the problem has overlapping subproblems, i.e. the optimal solution of smaller capacity and number of items can be reused to find the optimal solution of distinct larger capacities and numbers of items. Since the problem has optimal substructure and overlapping subproblems, then dynamic programming can be used to solve the problem.

Time Complexity

The algorithm iterates the capacity and number of items. Therefore, the time complexity of the algorithm is O(nc).

Space Complexity

The auxiliary space complexity depends on the size of the 2-D matrix which is n × c. Therefore, the auxiliary space complexity of the algorithm is O(nc).

Links

data_structures_algorithms/algorithms/dynamic_programming/knapsack_01 at main ·…