CONTENTS:

1. INTRODUCTION
2. ALGORITHM AND FLOWCHART
3. PROGRAM
4. MATHEMATICAL ANALYSIS
5. INPUT AND OUTPUT SPECIFICATION
6. CODE DEMONTRATION
1.INTRODUCTION

The 0/1 Knapsack problem is one of the most well-known and widely studied problems in
computer science and combinatorial optimization. The problem models a scenarios in which a
decision-maker must select a subset of items from a larger set to maximize profit subject to a
weight constraint. It has vast applications in resource allocation, budgeting, logistics, and many
other optimization problems.

This report explores the brute force solution to the 0/1 Knapsack problem. Although not the most
efficient, the brute force approach provides a foundational understanding of how exhaustive search
works and guarantees an optimal solution for small input sizes.

Problem Statement

1.You are given a set of n items. Each item has:

 A weight w[i]
 A value v[i]

2.You are also given a knapsack with a maximum weight capacity W.

3.The objective is to select a subset of items such that:

o The total weight does not exceed the knapsack’s capacity W.

4.The total value is maximized.

This is the classic 0/1 Knapsack problem because you can either take an item (1) or leave it (0)—
you cannot break or divide items.

Bruteforce approach
The brute force approach to solving the 0/1 Knapsack problem involves checking all possible
subsets of the given items to find the one that has the maximum total value without exceeding the
weight limit. This approach has exponential time complexity but is simple and guarantees the
optimal solution.For n items, there are 2^n possible subsets. Each subset can be evaluated for total
weight and value.
2.ALGORITHM AND FLOWCHART

2.1 Algorithm
Here is the pseudocode for the brute force method:

1. Initialize maxValue = 0

2. For each subset in 2^n:

a. Set totalWeight = 0

b. Set totalValue = 0

c. For each item j in subset:

- If item j is included:
- Add weight[j] to totalWeight

- Add value[j] to totalValue

d. If totalWeight <= W and totalValue > maxValue:

- Set maxValue = totalValue

3. Return maxValue
2.2 Flowchart

End
3.PROGRAM

from itertools import combinations

def knapsack_brute_force(weights, values, capacity): n = len(weights) max_value = 0

# Loop through all subsets using combinations

for i in range(1 << n): # 2^n combinations
total_weight = 0
total_value = 0
for j in range(n):
if (i >> j) & 1: # Check if j-th item is included
total_weight += weights[j]
total_value += values[j]
if total_weight <= capacity and total_value > max_value:
max_value = total_value

return max_value

weights = [2, 3, 4] values = [3, 4, 5] capacity = 5

result = knapsack_brute_force(weights, values, capacity)

print("Maximum value:", result)

4.MATHEMATICAL ANALYSIS
The brute force solution explores every possible combination of items to determine the optimal
subset that maximizes the total value without exceeding the knapsack's capacity.

1. Time Complexity

 For n items, there are 2ⁿ possible subsets. Each subset may include or exclude each item
independently.
 For each subset:
 We calculate the total weight and total value, which takes O(n) time.
 Total subsets: 2ⁿ
 Therefore, total time = O(n * 2ⁿ)
 This is exponential time complexity, which becomes computationally expensive for even
moderately large values of n (e.g., n > 20).

2. Space Complexity

 The space used in the brute force approach is mainly for:

 Storing weights and values: O(n)
 Tracking current subset information (e.g., total weight/value): O(1)
 No additional structures like matrices or lists for memoization are used.
 Thus, the space complexity is O(n).

3. Best Case

 Even in the best case (e.g., the first valid subset found is optimal), the brute force approach
still checks all combinations, because it has no way of knowing if a better one exists
without evaluating all.
 So, best-case time complexity = O(n * 2ⁿ)

4. Worst Case

 The algorithm evaluates all possible subsets.

 So, worst-case time complexity = O(n * 2ⁿ)

5. Average Case

 Since it evaluates all subsets regardless of input characteristics, the average-case time
complexity is also:
 O(n * 2ⁿ)

MetricValue

Time Complexity O(n * 2ⁿ)

Space Complexity O(n)

Best Case O(n * 2ⁿ)

Worst Case O(n * 2ⁿ)

Average Case O(n * 2ⁿ)

5.OUTPUT AND INPUT SPECIFICATIONS

Component Description
Input
Items A list of items, each with a weight and a value.
Weights w=[w1,w2,...,wn]w = [w_1, w_2, ..., w_n]
Values v=[v1,v2,...,vn]v = [v_1, v_2, ..., v_n]
WW: Maximum weight the knapsack can
Capacity
hold.
Number of items nn: Total number of items.
Output
The maximum total value possible without
Maximum value
exceeding capacity WW.
A list or subset of item indices that contribute
Selected items
to the maximum value.

Input Value
Items 3
Weights [10, 20, 30]
Values [60, 100, 120]
Capacity 50
Output
Maximum value 220
Items 2 and 3 (weights 20 +
Selected items 30 = 50, values 100 + 120 =
220)
6.CODE DEMONSTRATION