Redg.No.
22BQ1A1245 (Autonomous) VASIREDDY VENKATADRI INSTITUTE TECHNOLOGY VVIT
Exp NO:8 HGFHG
Aim: Implement 0/1 Dynamic knapsack problem (Tabulation method)
Source Code:
#include <stdio.h>
void knapsack(int n, int m, int profits[], int weights[]) {
int T[n + 1][m + 1];
int i;
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= m; j++) {
if (i == 0 || j == 0)
T[i][j] = 0;
else if (j - weights[i - 1]>=0)
if(T[i - 1][j]>profits[i - 1] + T[i - 1][j - weights[i - 1]])
T[i][j]=T[i-1][j];
else
T[i][j]=profits[i - 1] + T[i - 1][j - weights[i - 1]];
else
T[i][j] = T[i - 1][j];
}
}
int max_value = T[n][m];
printf("Max profit earned = %d\n", max_value);
int optimalPath[n];
for (i = 0; i < n; i++) {
optimalPath[i] = 0;
}
int tm = m;
for (i = n; i > 0 && tm > 0; i--) {
if (max_value != T[i - 1][tm]){
printf("Item %d is included (Profit: %d, Weight: %d)\n", i, profits[i - 1], weights[i - 1]);
optimalPath[i - 1] = 1;
tm -= weights[i - 1];
}}
printf("\nOptimal Path (0/1 format): ");
for (i = 0; i < n; i++) {
printf("%d ", optimalPath[i]);
}
DAA Programming Lab 1
Redg.No. 22BQ1A1245 (Autonomous) VASIREDDY VENKATADRI INSTITUTE TECHNOLOGY VVIT
printf("\n"); HGFHG
}
int main() {
int n, m;
printf("Enter number of items: ");
scanf("%d", &n);
printf("Enter the capacity of knapsack:");
scanf("%d",&m);
int profits[n], weights[n];
printf("Enter profits of items: \n");
for (int i = 0; i < n; i++)
scanf("%d", &profits[i]);
printf("Enter weights of items: \n");
for (int i = 0; i < n; i++)
scanf("%d", &weights[i]);
knapsack(n, m, profits,weights);
}
Output:
harshitha@victus:~$ gcc dynamicknapsack.c
harshitha@victus:~$ ./a.out
Enter number of items: 3
Enter the capacity of knapsack:6
Enter profits of items:
1
2
5
Enter weights of items:
2
3
4
Max profit earned = 6
Item 3 is included (Profit: 5, Weight: 4)
Item 2 is included (Profit: 2, Weight: 3)
Optimal Path (0/1 format): 0 1 1
DAA Programming Lab 2
Redg.No. 22BQ1A1245 (Autonomous) VASIREDDY VENKATADRI INSTITUTE TECHNOLOGY VVIT
Exp NO:9 HGFHG
Aim: Implement 0/1 Dynamic knapsack problem (Tabulation method)
Source Code:
#include <stdio.h>
#define N 4
int board[N][N];
int totalSol = 0;
int isSafe(int row, int col) {
for (int i = 0; i < row; i++) {
if (board[i][col] == 1) return 0;
}
for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
if (board[i][j] == 1) return 0;
}
for (int i = row - 1, j = col + 1; i >= 0 && j < N; i--, j++) {
if (board[i][j] == 1) return 0;
}
return 1;
}
void printSolution() {
printf("Solution:\n");
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (board[i][j] == 1) {
printf("Q ");
} else {
printf(". ");
}
}
printf("\n");
}
printf("\n");
}
void NQueens(int row) {
if (row == N) {
DAA Programming Lab 3
Redg.No. 22BQ1A1245 (Autonomous) VASIREDDY VENKATADRI INSTITUTE TECHNOLOGY VVIT
totalSol++; HGFHG
printf("Solution %d:\n", totalSol);
printSolution();
return;
}
for (int col = 0; col < N; col++) {
if (isSafe(row, col)) {
board[row][col] = 1;
NQueens(row + 1);
board[row][col] = 0;
}
}
}
int main() {
NQueens(0);
printf("Total solutions: %d\n", totalSol);
return 0;
}
Output:
harshitha@victus:~$ gcc nqueens.c
harshitha@victus:~$ ./a.out
Solution 1:
Solution:
.Q..
...Q
Q...
..Q.
Solution 2:
Solution:
..Q.
Q...
...Q
.Q..
Total solutions: 2
DAA Programming Lab 4
