Scribd
Upload
4 views6 pages

labb

The document outlines several optimization algorithms including Fractional Knapsack, Tree Vertex Splitting, Job Sequence with Deadlines, Coin Changing Algorithm, Machine Scheduling Algorithm, and Container Loading Algorithm. Each section includes a problem statement, analysis, algorithm overview, time and space complexity, code examples, and sample input/output. The algorithms primarily utilize greedy and dynamic programming approaches to solve various optimization problems.

Uploaded by

Rafik Rafik
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
4 views6 pages

labb

The document outlines several optimization algorithms including Fractional Knapsack, Tree Vertex Splitting, Job Sequence with Deadlines, Coin Changing Algorithm, Machine Scheduling Algorithm, and Container Loading Algorithm. Each section includes a problem statement, analysis, algorithm overview, time and space complexity, code examples, and sample input/output. The algorithms primarily utilize greedy and dynamic programming approaches to solve various optimization problems.

Uploaded by

Rafik Rafik
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/ 6

1.

Fractional Knapsack

1. Problem Statement
Maximize the value of items in a knapsack of a given capacity, where each item can be partially taken
(fractional).
2. Problem Analysis
 Input: List of items, each with a weight and value, and knapsack capacity.
 Objective: Select items to maximize value without exceeding capacity.
 Constraint: Items can be fractionally selected.
3. Algorithm Overview
1. Sort items by value-to-weight ratio.
2. Greedily select items in descending ratio order until capacity is full.
4. Time Complexity / Space Complexity
 TC: O(nlogn) (sorting items by ratio).
 SC: O(1) (constant extra space).
5. Code
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Item {
int value, weight;
Item(int v, int w) : value(v), weight(w) {}
double valuePerWeight() const { return (double)value / weight; }
};

double fractionalKnapsack(int W, vector<Item>& items) {


sort(items.begin(), items.end(), [](Item& a, Item& b) {
return a.valuePerWeight() > b.valuePerWeight();
});
double totalValue = 0.0;
for (auto& item : items) {
if (W >= item.weight) {
W -= item.weight;
totalValue += item.value;
} else {
totalValue += item.value * ((double)W / item.weight);
break;
}
}
return totalValue;
}

6. Sample Input / Output


 Input: Items: {(60, 10), (100, 20), (120, 30)}, Capacity: 50
 Output: Maximum value: 240
7. Remark
This algorithm demonstrates a greedy approach to optimization.

2. Tree Vertex Splitting

1. Problem Statement
Split a tree’s vertices with minimum cuts to satisfy certain properties (e.g., balance constraints or
spanning subtrees).
2. Problem Analysis
 Input: Tree structure with vertex properties.
 Objective: Minimize cuts while satisfying given vertex properties.
 Constraints: The tree should remain connected after splits.
3. Algorithm Overview
1. Use dynamic programming (DP) on trees.
2. For each subtree, calculate minimum cuts needed.
4. Time Complexity / Space Complexity
 TC: O(V+E) for traversal.
 SC: O(V) for DP storage.
5. Code
#include <iostream>
#include <vector>
using namespace std;

int minCuts(int node, const vector<vector<int>>& tree, vector<int>& dp) {


if (dp[node] != -1) return dp[node];
dp[node] = 0;
for (int child : tree[node]) {
dp[node] += minCuts(child, tree, dp);
}
return dp[node];
}

6. Sample Input / Output


 Input: Tree structure as adjacency list.
 Output: Minimum cuts to split.
7. Remark
Tree splitting is often used in network optimization and load balancing.
3. Job Sequence with Deadlines

1. Problem Statement
Maximize profit by scheduling jobs with deadlines and profits.
2. Problem Analysis
 Input: List of jobs with deadlines and profits.
 Objective: Schedule jobs within deadlines to maximize profit.
 Constraint: Jobs take unit time and must be done before deadlines.
3. Algorithm Overview
1. Sort jobs by profit.
2. Assign jobs to latest available slot before deadline.
4. Time Complexity / Space Complexity
 TC: O(nlogn) (sorting jobs).
 SC: O(n) (tracking time slots).
5. Code
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Job {
int id, deadline, profit;
};

bool compare(Job& a, Job& b) {


return a.profit > b.profit;
}

int jobSequence(vector<Job>& jobs, int n) {


sort(jobs.begin(), jobs.end(), compare);
vector<bool> slots(n, false);
int totalProfit = 0;
for (auto& job : jobs) {
for (int j = min(n, job.deadline) - 1; j >= 0; --j) {
if (!slots[j]) {
slots[j] = true;
totalProfit += job.profit;
break;
}
}
}
return totalProfit;
}

6. Sample Input / Output


 Input: Jobs: {(1, 4, 20), (2, 1, 10), (3, 1, 40), (4, 1, 30)}
 Output: Maximum profit: 60
7. Remark
This approach leverages greedy selection based on profit.

4. Coin Changing Algorithm

1. Problem Statement
Find the minimum number of coins needed to make a target amount.
2. Problem Analysis
 Input: Coin denominations and target amount.
 Objective: Minimize coins used.
 Constraints: Coins may not perfectly sum to amount.
3. Algorithm Overview
1. Use DP array to track minimum coins needed for each amount.
2. For each coin, update DP array for reachable amounts.
4. Time Complexity / Space Complexity
 TC: O(n×m)
 SC: O(n)
5. Code
#include <iostream>
#include <vector>
using namespace std;

int minCoins(vector<int>& coins, int amount) {


vector<int> dp(amount + 1, amount + 1);
dp[0] = 0;
for (int i = 1; i <= amount; ++i) {
for (int coin : coins) {
if (i - coin >= 0)
dp[i] = min(dp[i], dp[i - coin] + 1);
}
}
return dp[amount] > amount ? -1 : dp[amount];
}

6. Sample Input / Output


 Input: Coins: [1, 2, 5], Amount: 11
 Output: Minimum coins required: 3
7. Remark
This DP approach ensures optimal solution by solving subproblems.
5. Machine Scheduling Algorithm

1. Problem Statement
Assign jobs to machines to minimize overall job completion time or machine idle time.
2. Problem Analysis
 Input: Job durations and machines.
 Objective: Balance workload across machines.
 Constraints: Minimize completion time.
3. Algorithm Overview
1. Sort jobs by duration.
2. Greedily assign jobs to the least loaded machine.
4. Time Complexity / Space Complexity
 TC: O(nlogn) (sorting jobs).
 SC: O(m) (tracking machine loads).
5. Code
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int machineScheduling(vector<int>& jobs, int m) {


priority_queue<int, vector<int>, greater<int>> machines;
for (int i = 0; i < m; ++i) machines.push(0);
for (int job : jobs) {
int minMachine = machines.top(); machines.pop();
minMachine += job;
machines.push(minMachine);
}
int maxTime = 0;
while (!machines.empty()) {
maxTime = max(maxTime, machines.top());
machines.pop();
}
return maxTime;
}

6. Sample Input / Output


 Input: Jobs: [2, 3, 7, 10], Machines: 2
 Output: Minimum completion time: 13
7. Remark
Using priority queue helps balance loads.
6. Container Loading Algorithm

1. Problem Statement
Maximize the weight loaded into containers without exceeding capacity.
2. Problem Analysis
 Input: List of container capacities and item weights.
 Objective: Maximize loaded weight.
 Constraints: Weight per container should not exceed capacity.
3. Algorithm Overview
1. Sort items by weight.
2. Greedily fill containers until capacity is reached.
4. Time Complexity / Space Complexity
 TC: O(nlogn)
 SC: O(1)
5. Code
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int maxLoad(vector<int>& containers, vector<int>& items) {


sort(containers.rbegin(), containers.rend());
sort(items.rbegin(), items.rend());
int loadedWeight = 0;
for (int i = 0, j = 0; i < containers.size() && j < items.size(); ++i) {
while (j < items.size() && items[j] <= containers[i]) {
loadedWeight += items[j++];
}
}
return loadedWeight;
}

6. Sample Input / Output


 Input: Containers: [10, 15], Items: [5, 7, 8]
 Output: Maximum weight loaded: 15
7. Remark
Greedy loading strategy ensures maximum weight distribution.

You might also like