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

Lab 7-1

Lab

Uploaded by

narutouzmaki86888
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
18 views2 pages

Lab 7-1

Lab

Uploaded by

narutouzmaki86888
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

7))Implement 0/1 Knapsack problem using Dynamic Programming and output

its
time complexity

#include <stdio.h>
#include <stdlib.h>

// Function to find the maximum of two integers


int max(int a, int b) {
return (a > b) ? a : b;
}

// Function to implement the 0/1 Knapsack problem using Dynamic Programming


int knapsack(int W, int wt[], int val[], int n) {
int i, w;
int dp[n + 1][W + 1];

// Build the dp table in bottom-up manner


for (i = 0; i <= n; i++) {
for (w = 0; w <= W; w++) {
if (i == 0 || w == 0)
dp[i][w] = 0;
else if (wt[i - 1] <= w)
dp[i][w] = max(val[i - 1] + dp[i - 1][w - wt[i - 1]], dp[i - 1][w]);
else
dp[i][w] = dp[i - 1][w];
}
}

return dp[n][W];
}

int main() {
int n, W;

// Take input for the number of items and knapsack capacity


printf("Enter the number of items: ");
scanf("%d", &n);
printf("Enter the knapsack capacity: ");
scanf("%d", &W);

int *val = (int *)malloc(n * sizeof(int));


int *wt = (int *)malloc(n * sizeof(int));

// Take input for the values and weights of the items


for (int i = 0; i < n; i++) {
printf("Enter value and weight for item %d: ", i + 1);
scanf("%d %d", &val[i], &wt[i]);
}

int maxValue = knapsack(W, wt, val, n);


printf("Maximum value in Knapsack = %d\n", maxValue);

// Time Complexity: O(nW)


printf("Time Complexity = O(%d*%d)\n", n, W);

// Free dynamically allocated memory


free(val);
free(wt);

return 0;
}

Output
Enter the number of items: 4
Enter the knapsack capacity: 50
Enter value and weight for item 1: 60 10
Enter value and weight for item 2: 100 20
Enter value and weight for item 3: 120 30
Enter value and weight for item 4: 80 40
Maximum value in Knapsack = 220
Time Complexity = O(4*50)

You might also like