Scribd
Upload
21 views2 pages

Student Name: Harsh Kumar Singh: Experiment-2.3

The document summarizes a student's experiment on implementing the 0-1 Knapsack problem using dynamic programming. The student implemented a 0-1 Knapsack algorithm that uses a DP table to store the maximum values for all possible weight combinations in a bottom-up manner. The algorithm returns the maximum value that can be achieved for a given capacity W by considering items weights and values. The student's code successfully implements this dynamic programming solution to 0-1 Knapsack and returns the maximum value of 325 for the given sample input.

Uploaded by

Ashish Goswami
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
21 views2 pages

Student Name: Harsh Kumar Singh: Experiment-2.3

The document summarizes a student's experiment on implementing the 0-1 Knapsack problem using dynamic programming. The student implemented a 0-1 Knapsack algorithm that uses a DP table to store the maximum values for all possible weight combinations in a bottom-up manner. The algorithm returns the maximum value that can be achieved for a given capacity W by considering items weights and values. The student's code successfully implements this dynamic programming solution to 0-1 Knapsack and returns the maximum value of 325 for the given sample input.

Uploaded by

Ashish Goswami
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

Student Name: Harsh Kumar Singh UID: 21BCS11624

Branch: CSE Section/Group: 608-B


Semester: 5th Date of Performance: 05-10-2023
Subject Name: DAA Lab Subject Code: 21CSH-311

Experiment-2.3

1. Aim: Develop a program and analyze complexity to implement 0-1 Knapsack using Dynamic
Programming

2. Objective: To implement 0-1 Knapsack using Dynamic Programming


3. Procedure:
In the Dynamic programming we will work considering the same cases as mentioned in the recursive approach.
In a DP[][] table let’s consider all the possible weights from ‘1’ to ‘W’ as
the
columns and weights that can be kept as the rows.
The state DP[i][j] will denote the maximum value of ‘j-weight’ considering all values from ‘1 to ith’.
So if we consider ‘wi’ (weight in ‘ith’ row) we can fill it in all columns which have weight values > wi’. Now two
possibilities can take place:
● Fill ‘wi’ in the given column.
● Do not fill ‘wi’ in the given column.
Now we have to take a maximum of these two possibilities, formally if we do not fill ‘ith’weight
in ‘jth’ column then DP[i][j] state will be same as DP[i-1][j] but if we fill the weight, DP[i][j] will be equal to the
value of ‘wi’+ value of the column weighing ‘j-wi’ in the previous row. So we take the maximum of these two
possibilities to fill the current state. This visualization will make the concept clear:
Let weight elements = {1, 2, 3}
Let weight values = {10, 15, 40} Capacity=6
0123456
00000000
1 0 10 10 10 10 10 10
2 0 10 15 25 25 25 25

4. Script and Output:


#include<stdio.h> int max(int a, int b)
{
return (a > b)? a : b;
}
int knapSack(int W, int wt[], int val[], int n)
{
int i, w;
int K[n+1][W+1];
// Build table K[][] in bottom up manner

for (i = 0; i <= n; i++)


{
for (w = 0; w <= W; w++)
{
if (i==0 ||w==0) K[i][w] = 0;
else if (wt[i-1] <= w)
K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]],
K[i-1][w]);else K[i][w] = K[i-1][w];
}
}
return K[n][W];
}
int main()
{
int val[] = {50, 175, 100};
int wt[] = {10, 20, 30};
int W = 50;
int n = sizeof(val)/sizeof(val[0]);
printf("%d", knapSack(W, wt, val, n));
return 0;
}

5. Output:

You might also like