[go: up one dir, main page]
Scribd
Upload
7 views4 pages

Algo lab5

The lab report presents two algorithms: the Knapsack problem and the Rod Cutting problem, both implemented in C++. The Knapsack algorithm calculates the maximum value obtainable given weights and values of items, while the Rod Cutting algorithm determines the maximum profit from cutting a rod of a specified length. Each algorithm includes explanations of the dynamic programming approach used and their respective time complexities.

Uploaded by

Arman Danesh
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
7 views4 pages

Algo lab5

The lab report presents two algorithms: the Knapsack problem and the Rod Cutting problem, both implemented in C++. The Knapsack algorithm calculates the maximum value obtainable given weights and values of items, while the Rod Cutting algorithm determines the maximum profit from cutting a rod of a specified length. Each algorithm includes explanations of the dynamic programming approach used and their respective time complexities.

Uploaded by

Arman Danesh
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

LAB REPORT

Course Title : Algorithms LAB


Course Code : CSE 232
LAB No : 05

Submitted By: Submitted To:


Name: Sabit Hasan Badhon Name: Sajid Ahmed
ID No: 20234103014 Chowdhury
Intake: 52 Department of: CSE
Section: 01 Bangladesh University of
Program: B.Sc in CSE Business & Technology.

Date of Submission:
04-03-2025
Signature of Teacher
1.
#include <iostream>
#include <vector>
using namespace std;

int knapsack(int N, int W, vector<int>& weights, vector<int>& values) {


vector<vector<int>> dp(N + 1, vector<int>(W + 1, 0));
for (int i = 1; i <= N; ++i) {
for (int w = 1; w <= W; ++w) {
if (weights[i - 1] <= w) {
dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);
} else {
dp[i][w] = dp[i - 1][w];
}
}
}
return dp[N][W];
}
void printSelectedItems(int N, int W, vector<int>& weights, vector<int>& values) {
vector<vector<int>> dp(N + 1, vector<int>(W + 1, 0));
for (int i = 1; i <= N; ++i) {
for (int w = 1; w <= W; ++w) {
if (weights[i - 1] <= w) {
dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);
} else {
dp[i][w] = dp[i - 1][w];
}
}
}
int w = W;
vector<int> selectedItems;
for (int i = N; i > 0; --i) {
if (dp[i][w] != dp[i - 1][w]) {
selectedItems.push_back(i);
w -= weights[i - 1];
}
}
cout << "Selected items: ";
for (int i = selectedItems.size() - 1; i >= 0; --i) {
cout << selectedItems[i] << " ";
}
cout << endl;
}

int main() {
int N, W;
cout << "Enter the number of items: ";
cin >> N;
cout << "Enter the capacity of the knapsack: ";
cin >> W;
vector<int> weights(N), values(N);
cout << "Enter the weights of the items: ";
for (int i = 0; i < N; ++i) {
cin >> weights[i];
}
cout << "Enter the values of the items: ";
for (int i = 0; i < N; ++i) {
cin >> values[i];
}
int maxValue = knapsack(N, W, weights, values);
cout << "Maximum value: " << maxValue << endl;
printSelectedItems(N, W, weights, values);

return 0;
}

Explanation:
1. DP Table Construction: We construct the DP table dp[i][w] where i represents the
number of items considered, and w represents the current weight capacity of the knapsack.
The value of dp[i][w] is computed based on whether we include or exclude the i-th item.
2. Backtracking: After constructing the table, we trace back from dp[N][W] to find which
items were included in the optimal solution. This is done by checking if the current value
is different from the value in the previous row at the same capacity. If they are different, it
means the item i was included.
Explanation of Output:
• The maximum value we can obtain is 80.
• The selected items are 1 and 2 (using 3 units and 4 units of weight respectively, yielding
values of 30 and 50).

2.
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int rodCutting(int N, vector<int>& prices) {


vector<int> dp(N + 1, 0);
for (int i = 1; i <= N; i++) {
for (int j = 0; j < i; j++) {
dp[i] = max(dp[i], prices[j] + dp[i - (j+1)]);
}
}
return dp[N];
}

int main() {
vector<int> prices = {2, 5, 7, 8, 10};
int N = prices.size();
cout<< "Maximum Profit:"<<rodCutting(N,prices)<<endl;
return 0;
}

Explanation:
1. maxProfit Function:
o Takes the length of the rod N and the prices array as input.
o Initializes a dp array of size N+1 where each element dp[i] stores the maximum
profit obtainable from a rod of length i.
o For each rod length i, iterates over all possible cuts j and computes the maximum
profit by considering both the price of the segment of length j and the best
possible profit for the remaining length i-j.
o Finally, dp[N] gives the maximum profit for a rod of length N.
2. main Function:
o Runs the algorithm with two test cases and prints the results.
Time Complexity:
• The time complexity of this approach is O(N^2) because we are using two nested loops,
where the outer loop runs for i from 1 to N, and the inner loop runs for j from 1 to i.

You might also like