LAB PROGRAM-4
Implement in C/C++, the 0/1 Knapsack problem using (a) Dynamic Programming
method (b) Greedy method.
(a) Dynamic Programming method:
The 0/1 Knapsack problem can be solved using dynamic programming in polynomial
time. The idea is to create a table where the rows represent the items and the columns
represent the capacity of the knapsack. The value in each cell represents the maximum
value that can be obtained with the given items and capacity.
Algorithm:
1. Create a table with n rows (one for each item) and W+1 columns (one for each
possible weight from 0 to W).
2. Initialize the first row and first column to 0.
3. For each item i, and each weight w, calculate the maximum value that can be
obtained by either including or excluding the item. a. If the weight of the item is
less than or equal to w, then the maximum value that can be obtained is the
maximum of: i. The value of the current item + the maximum value that can be
obtained using the remaining items and the remaining capacity (w - weight of the
current item). ii. The maximum value that can be obtained using the remaining
items and the current capacity w. b. If the weight of the item is greater than w, then
the maximum value that can be obtained is the same as the maximum value that
can be obtained using the remaining items and the current capacity w.
4. The value in the last row and last column of the table is the maximum value that
can be obtained with the given items and capacity.
(a) Dynamic Programming method
#include <stdio.h>
#include <stdlib.h>
int max(int a, int b) {
return (a > b) ? a : b;
}
int knapsackDP(int n, int W, int wt[], int val[]) {
int i, j;
int dp[n+1][W+1];
for(i = 0; i <= n; i++) {
for(j = 0; j <= W; j++) {
if(i == 0 || j == 0)
dp[i][j] = 0;
else if(wt[i-1] <= j)
dp[i][j] = max(val[i-1] + dp[i-1][j-wt[i-1]], dp[i-1][j]);
else
dp[i][j] = dp[i-1][j];
}
}
return dp[n][W];
}
int main() {
int n, W, i;
printf("Enter the number of items: ");
scanf("%d", &n);
int val[n], wt[n];
printf("Enter the weight and value of each item:\n");
for(i = 0; i < n; i++)
scanf("%d%d", &wt[i], &val[i]);
printf("Enter the maximum weight capacity of the knapsack: ");
scanf("%d", &W);
printf("The maximum value that can be obtained is: %d", knapsackDP(n, W, wt, val));
return 0;
}
OUTPUT:
Enter the number of items: 3
Enter the weight and value of each item:
10 60
20 100
30 120
Enter the maximum weight capacity of the knapsack: 50
The maximum value that can be obtained is: 220
(b) Greedy method.
#include <stdio.h>
#include <stdlib.h>
typedef struct {
int weight;
int value;
float ratio;
} Item;
int compare(const void *a, const void *b) {
Item *item1 = (Item *)a;
Item *item2 = (Item *)b;
if (item2->ratio > item1->ratio) return 1;
else if (item2->ratio < item1->ratio) return -1;
else return 0;
}
int knapsackGreedy(int n, int W, Item items[]) {
// Sort items by value-to-weight ratio (descending)
qsort(items, n, sizeof(Item), compare);
int totalValue = 0;
int totalWeight = 0;
printf("\nItems selected (0/1 Greedy):\n");
printf("Index\tWeight\tValue\n");
for (int i = 0; i < n && W > 0; i++) {
if (items[i].weight <= W) {
W -= items[i].weight;
totalValue += items[i].value;
totalWeight += items[i].weight;
printf("%d\t%d\t%d\n", i + 1, items[i].weight, items[i].value);
}
}
printf("\nTotal weight used: %d\n", totalWeight);
return totalValue;
}
int main() {
int n, W;
printf("Enter the number of items: ");
scanf("%d", &n);
Item items[n];
printf("Enter the weight and value of each item:\n");
for (int i = 0; i < n; i++) {
printf("Item %d (weight value): ", i + 1);
scanf("%d%d", &items[i].weight, &items[i].value);
items[i].ratio = (float)items[i].value / items[i].weight;
}
printf("Enter the maximum weight capacity of the knapsack: ");
scanf("%d", &W);
int result = knapsackGreedy(n, W, items);
printf("Approximate maximum value (Greedy method): %d\n", result);
return 0;
}
OUTPUT:
Enter the number of items: 3
Enter the weight and value of each item:
Item 1 (weight value): 10 60
Item 2 (weight value): 20 100
Item 3 (weight value): 30 120
Enter the maximum weight capacity of the knapsack: 50
Items selected (0/1 Greedy):
Index Weight Value
1 10 60
2 20 100
Total weight used: 30
Approximate maximum value (Greedy method): 160
