Scribd
Upload
7 views4 pages

External

The document contains a C program that implements the 0/1 knapsack problem using dynamic programming. It reads the number of items and the maximum weight capacity, then calculates the maximum profit and selected items based on their weights and values. The program outputs the maximum profit and the details of the selected items.

Uploaded by

brijendra50444
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
7 views4 pages

External

The document contains a C program that implements the 0/1 knapsack problem using dynamic programming. It reads the number of items and the maximum weight capacity, then calculates the maximum profit and selected items based on their weights and values. The program outputs the maximum profit and the details of the selected items.

Uploaded by

brijendra50444
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

Brijendra Srivastava

CSIT-5A
2300290110066

External practical
0/1 knapsack problem:
CODE:
#include <stdio.h>

int max(int a, int b) {


return (a > b) ? a : b;
}

int main() {
int n, W;

if (scanf("%d %d", &n, &W) != 2) return 0;

int val[n], wt[n];


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

int dp[n + 1][W + 1];

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


for (int 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];
}
}

printf("Maximum Profit: %d\n", dp[n][W]);


printf("Selected Items (Weight, Value): \n");
int res = dp[n][W];
int w = W;
for (int i = n; i > 0 && res > 0; i--) {
if (res == dp[i - 1][w])
continue;
else {
printf("Item %d: (%d, %d)\n", i, wt[i - 1], val[i - 1]);
res = res - val[i - 1];
w = w - wt[i - 1];
}
}

return 0;
}
OUTPUT:

You might also like