[go: up one dir, main page]
Scribd
Upload
6 views2 pages

Experiment No 4 Write Up

The document outlines an experiment to implement and analyze the 0/1 knapsack problem using dynamic programming. It describes the algorithm for solving the problem, including the creation of a 2D array and the steps to fill it, ultimately returning the maximum value. The time complexity of the solution is analyzed as O(N * W), where N is the number of items and W is the weight capacity.

Uploaded by

30,XI,Aarya Shimpi
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
6 views2 pages

Experiment No 4 Write Up

The document outlines an experiment to implement and analyze the 0/1 knapsack problem using dynamic programming. It describes the algorithm for solving the problem, including the creation of a 2D array and the steps to fill it, ultimately returning the maximum value. The time complexity of the solution is analyzed as O(N * W), where N is the number of items and W is the weight capacity.

Uploaded by

30,XI,Aarya Shimpi
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

EXPERIMENT NO.

04

Aim: Write a program for 0/1 knapsack problem, analyze it, and find time
complexity.

Theory:
The 0/1 knapsack problems involves selecting items with weights and
values to maximize values without exceeding a weight limit solutions
include dynamic programming, which iteratively fills a table to find the
optimal solutions. It is called “0/1” because items cannot be partially
taken ,they are either included entirely or not at all included .

For example, we have two items having weights 2kg and 3kg,
respectively. If we pick the 2kg item then we cannot pick 1kg item from
the 2kg item (item is not divisible); we must pick the 2kg item
completely. This is a 0/1 knapsack problem in which either we pick the
item completely or we will not pick that item. The 0/1 knapsack problem
is solved by the dynamic programming.

ALGORITHM (Dynamic Programming Approach)

Function Knapsack (W, weight[], value[], N):


Create a 2D array dp[N+1][W+1]

# Step 1: Initialize the base case


For i from 0 to N:
For w from 0 to W:
If i == 0 OR w == 0:
dp[i][w] = 0 # No items or zero capacity

# Step 2: Build the DP table


For i from 1 to N:
For w from 1 to W:
If weight[i-1] ≤ w: # If item can be included
dp[i][w] = max(dp[i-1][w], value[i-1] + dp[i-1][w - weight[i-1]])
Else:
dp[i][w] = dp[i-1][w] # Exclude the item

# Step 3: Return the maximum value at dp[N][W]


Return dp[N][W]
Time Complexity Analysis:

Time complexity analysis of the 0/1 knapsack problem using dynamic


programming approach involves examining the no.of operations performed to fill
the dynamic programming table.

Time Complexity: O (N * W)

 Iterates through all items (N).


 Iterates through all weight capacities (W).

PROGRAM:

OUTPUT: (OUTPUT MUST BE TAKEN FOR BEST CASE , AVERAGE


CASE AND WORST CASE)

Conclusion:
Hence, We successfully implemented Knapsack problem.

You might also like