Scribd
Upload
9 views

Ex 6-Design and Analysis of Algorithms

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
9 views

Ex 6-Design and Analysis of Algorithms

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
You are on page 1/ 4

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