Scribd
Upload
16 views4 pages

Ex 6-Design and Analysis of Algorithms

The document presents a solution to the 0/1 knapsack problem using dynamic programming, including source code in C. It outlines the implementation of the knapsack function, which calculates the maximum profit and identifies the included items based on their weights and profits. An example execution is provided, demonstrating the input and output of the program.

Uploaded by

iamgowthamyt
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
16 views4 pages

Ex 6-Design and Analysis of Algorithms

The document presents a solution to the 0/1 knapsack problem using dynamic programming, including source code in C. It outlines the implementation of the knapsack function, which calculates the maximum profit and identifies the included items based on their weights and profits. An example execution is provided, demonstrating the input and output of the program.

Uploaded by

iamgowthamyt
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

Design and Analysis of Algorithms

Course Code: 19z402

Submitted by:

Gowtham P
22z325
BE - CSE(G2)
PSG College of Technology
Coimbatore.

Date : 02 . 05 . 2024
Exercise: 6 : 0/1 knapsack Problem using Dynamic programming

Source code:

#include<stdio.h>

#define max(a, b) ((a > b) ? a : b)

int knapsack(int capacity, int weights[], int values[],


int n) {
int i, w;
int dp[n+1][capacity+1];

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


for (w = 0; w <= capacity; w++) {
if (i == 0 || w == 0)
dp[i][w] = 0;
else if (weights[i-1] <= w)
dp[i][w] = max(values[i-1] +
dp[i-1][w-weights[i-1]], dp[i-1][w]);
else
dp[i][w] = dp[i-1][w];
}
}

int result = dp[n][capacity];


int includedItems[n];
i = n;
w = capacity;
int k = 0;
while (i > 0 && w > 0) {
if (dp[i][w] != dp[i-1][w]) {
includedItems[k++] = i-1;
w -= weights[i-1];
}
i--;
}

printf("Items included in the knapsack:\n");


for (i = k - 1; i >= 0; i--)
printf("Item %d (Weight: %d, Profit: %d)\n",
includedItems[i] + 1, weights[includedItems[i]],
values[includedItems[i]]);

return result;
}

int main() {
int W, n;

printf("Enter the number of items: ");


scanf("%d", &n);

int weights[n], profits[n];

printf("Enter the weights of the items:\n");


for (int i = 0; i < n; i++)
scanf("%d", &weights[i]);

printf("Enter the profits of the items:\n");


for (int i = 0; i < n; i++)
scanf("%d", &profits[i]);

printf("Enter the capacity of the knapsack: ");


scanf("%d", &W);

int max_value = knapsack(W, weights, profits, n);


printf("Maximum Profit in the knapsack: %d\n",
max_value);
return 0;
}
Output:

Enter the number of items: 5


Enter the weights of the items:
1 3 4 5 6
Enter the profits of the items:
9 5 1 6 4
Enter the capacity of the knapsack: 12
Items included in the knapsack:
Item 1 (Weight: 1, Profit: 9)
Item 2 (Weight: 3, Profit: 5)
Item 4 (Weight: 5, Profit: 6)
Maximum Profit in the knapsack: 20

Process returned 0 (0x0) execution time : 23.582 s


Press any key to continue.

You might also like